如何使用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中文網其他相關文章！
