拓扑排序 - 创建有向图问题

拓扑排序是一种对有向无环图（DAG）进行排序的算法。它的基本思想是通过不断删除入度为0的顶点来排序，直到所有顶点都被排序。以下是一种用于创建有向图并进行拓扑排序的示例解决方法：

from collections import defaultdict

class Graph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.graph = defaultdict(list)

    def add_edge(self, u, v):
        self.graph[u].append(v)

    def topological_sort_util(self, v, visited, stack):
        visited[v] = True

        for neighbor in self.graph[v]:
            if not visited[neighbor]:
                self.topological_sort_util(neighbor, visited, stack)

        stack.append(v)

    def topological_sort(self):
        visited = [False] * self.num_vertices
        stack = []

        for i in range(self.num_vertices):
            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)

# 进行拓扑排序
result = g.topological_sort()
print("拓扑排序结果：", result)

输出结果为：

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

在该示例中，我们首先创建了一个有向图，并添加了一些边。然后，我们调用 topological_sort() 方法进行拓扑排序。在 topological_sort() 方法中，我们首先创建一个空的栈和一个布尔数组 visited 来跟踪已访问的顶点。然后，我们遍历所有顶点，对未访问的顶点调用 topological_sort_util() 方法进行深度优先搜索。在 topological_sort_util() 方法中，我们首先将当前顶点标记为已访问，并递归访问所有邻居顶点。最后，我们将当前顶点压入栈中。最后，我们返回栈的逆序，即为拓扑排序的结果。