如何使用Python實作拓樸排序演算法？

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