有向有环图进行排序的算法(拓扑法)

拓扑排序算法是一种用于有向图的排序方法，它可以对有向无环图（DAG）进行排序。这种排序是将图中的顶点排成一个线性序列，使得图中的任意一对顶点 u 和 v，如果存在边 u -> v，那么在排序后 u 出现在 v 之前。

以下是拓扑排序的经典算法，通常使用深度优先搜索（DFS）实现：

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.graph = defaultdict(list)  # 邻接表表示图
        self.V = 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 not visited[i]:
                self.topological_sort_util(i, visited, stack)

        stack.append(v)

    # 执行拓扑排序
    def topological_sort(self):
        visited = [False] * self.V
        stack = []

        for i in range(self.V):
            if not visited[i]:
                self.topological_sort_util(i, visited, stack)

        return stack[::-1]  # 返回逆序的拓扑排序结果

# 示例用法
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)

print("拓扑排序结果：", g.topological_sort())

拓扑排序结果： [5, 4, 2, 3, 1, 0]

这个示例首先创建了一个图，然后通过 add_edge 方法添加边。topological_sort 方法执行了拓扑排序，最后输出排序结果。

拓扑排序算法使用了深度优先搜索，先访问图中的节点，并在访问完一个节点后将其添加到栈中。最终栈中的顺序即为拓扑排序的结果。

需要注意的是，拓扑排序只适用于有向无环图（DAG）。如果图中存在环路，则无法进行拓扑排序。