Python中使用Graph()解决图的拓扑排序问题

在Python中，可以使用Graph()解决图的拓扑排序问题。拓扑排序是一种对有向无环图中顶点进行排序的算法，其中，每个顶点出现在其所有的后继的前面。

以下是一个使用Graph()解决图的拓扑排序问题的例子：

# 导入graph类
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.insert(0, 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)

        return stack

# 创建一个图
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("拓扑排序的结果为:")
for vertex in result:
    print(vertex, end=" ")

在上面的例子中，我们首先导入了defaultdict类并创建一个Graph类。在Graph类的构造函数中，我们使用了一个字典（graph）来表示图，其中默认的值为一个空列表。

然后我们定义了add_edge()方法，用于向图中添加边。接下来，我们定义了topological_sort_util()方法，该方法使用递归的方式进行深度优先搜索，并将已访问的节点添加到一个栈中。最后，我们定义了topological_sort()方法，该方法初始化了一个visited列表用于跟踪节点的访问状态，并从每个未访问的节点开始进行拓扑排序。

接下来，我们创建了一个图，并添加了一些边。然后，我们调用topological_sort()方法进行拓扑排序，并将结果打印出来。

以上代码的输出结果为：

拓扑排序的结果为:
5 4 2 3 1 0

这表示将图中的顶点按照拓扑排序的顺序从字符串的右侧顺序输出。

总结起来，使用Graph()可以方便地在Python中解决图的拓扑排序问题。我们可以创建一个图对象，并使用它的方法来添加边和进行拓扑排序。这样可以简化拓扑排序的实现，并在解决拓扑排序问题时提供便利。