如何使用Python實作拓樸排序演算法？
拓樸排序是圖論中的一種排序演算法，用於對有向無環圖（DAG）進行排序。在拓樸排序中，圖中的節點代表任務或事件，有向邊表示任務或事件之間的依賴關係。在排序結果中，所有的依賴關係都被滿足，每個節點都排在它的所有前驅節點之後。
在Python中實作拓樸排序演算法可以使用深度優先搜尋（DFS）的想法來解決。以下是一個具體的程式碼範例：
from collections import defaultdict class Graph: def __init__(self, num_vertices): self.graph = defaultdict(list) self.num_vertices = num_vertices def add_edge(self, u, v): self.graph[u].append(v) def topological_sort_util(self, v, visited, stack): visited[v] = True for i in self.graph[v]: if visited[i] == False: self.topological_sort_util(i, visited, stack) stack.append(v) def topological_sort(self): visited = [False] * self.num_vertices stack = [] for i in range(self.num_vertices): if visited[i] == False: self.topological_sort_util(i, visited, stack) sorted_list = [] while stack: sorted_list.append(stack.pop()) return sorted_list # 测试代码 g = Graph(6) g.add_edge(5, 2) g.add_edge(5, 0) g.add_edge(4, 0) g.add_edge(4, 1) g.add_edge(2, 3) g.add_edge(3, 1) sorted_list = g.topological_sort() print("拓扑排序结果：", sorted_list)
以上程式碼首先定義了一個Graph類，其中包含了新增邊、拓樸排序等方法。在拓樸排序過程中，使用了深度優先搜尋來遍歷圖中的節點。透過使用一個堆疊來儲存已被存取過的節點，最後可以得到按照拓樸排序規則排列的節點清單。
上述程式碼也包含了一個簡單的測試案例，用來檢驗拓樸排序演算法的正確性。在這個測試案例中，定義了一個大小為6的圖，並加入了一些節點和邊。最後，列印出經過拓樸排序後的節點清單。
使用Python實作拓樸排序演算法可以方便地處理圖中的依賴關係，對任務調度等問題有很大的幫助。透過理解和運用這項演算法，可以更好地解決實際問題。希望本文對你有幫助。
以上是如何使用Python實作拓樸排序演算法？的詳細內容。更多資訊請關注PHP中文網其他相關文章！
