題目出處

127 · Topological Sorting

難度

medium

個人範例程式碼 – 2022/6/7 二刷

"""
class DirectedGraphNode:
     def __init__(self, x):
         self.label = x
         self.neighbors = []
"""

class Solution:
    """
    @param graph: A list of Directed graph node
    @return: Any topological order for the given graph.
    """
    def topSort(self, graph):
        # write your code here
        if not graph:
            return []

        degree = self.get_degree(graph)
        return self.topological_sort(degree, graph)

    def topological_sort(self, degree, graph):
        ans = []
        visited = set()
        start_nodes = [node for node in degree if degree[node] == 0]
        queue = start_nodes

        while queue:
            node = queue.pop(0)
            ans.append(node)
            visited.add(node)
            for neighbor in node.neighbors:
                degree[neighbor] -= 1
                if neighbor not in visited and degree[neighbor] == 0:
                    queue.append(neighbor)

        return ans

    def get_degree(self, graph):
        degree = collections.defaultdict(int)
        for node in graph:
            if node not in degree:
                degree[node] = 0
            for neighbor in node.neighbors:
                degree[neighbor] += 1

        return degree

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

算法說明

考 BFS 中的拓樸排序法，BFS 經典問題

input handling

如果沒有 graph，直接回傳 []

Boundary conditions

透過 queue 來控制 BFS 結束的時間。

個人範例程式碼 – 2022/4/19 一刷

"""
class DirectedGraphNode:
     def __init__(self, x):
         self.label = x
         self.neighbors = []
"""

class Solution:
    """
    @param graph: A list of Directed graph node
    @return: Any topological order for the given graph.
    """
    def topSort(self, graph):
        # write your code here
        node_to_indegree = self.get_indegree(graph)

        order = []
        start_nodes = [n for n in graph if node_to_indegree == 0]
        queue = collections.deque(start_nodes)

        while queue:
            node = queue.popleft()
            order.append(node)
            for neighbor in node.neighbors:
                node_to_indegree[neighbor] -= 1
                if node_to_indegree[neighbor] == 0:
                    queue.append(neighbor)

        return order

    def get_indegree(self, graph):
        node_to_indegree = {node: node for x in graph}

        for node in graph:
            for neighbor in node.neightbors:
                node_to_indegree[neighbor] += 1

        return node_to_indegree

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

算法說明

這題考的是 BFS 中的拓樸排序法，個人認為比較難的是在 graph 操作的部分，其他的概念相對來說還好。

另外處理 start_courses ，去尋找 indegree 為 0 的 node

input handling

x

Boundary conditions

當 queue 為空時，結束迴圈，並回傳順序

indegree, outdegree 介紹

直接講重點，就是當我們在看有向圖時，

• 「往 node 進入」：就算一次 indegree (記法：就是 in 嘛…)
• 「自 node 出去」：就算一次 outdegree (記法：就是 out 嘛…)

例圖

(借用 google 的圖，Source：Figure 3 – uploaded by Sameer Kumar)：

很推薦大家去看下面這部影片，一看就懂：

Reference

• 拓扑排序 · Topological Sorting