python实现拓扑排序
时间: 2023-09-14 09:09:55 浏览: 229
拓扑排序是一种对有向无环图(DAG)进行排序的算法。在Python中,可以使用深度优先搜索(DFS)或广度优先搜索(BFS)来实现拓扑排序。
以下是使用深度优先搜索(DFS)算法实现拓扑排序的示例代码:
```python
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 dfs(self, v, visited, stack):
visited[v] = True
for neighbor in self.graph[v]:
if not visited[neighbor]:
self.dfs(neighbor, visited, stack)
stack.append(v)
# 拓扑排序函数
def topological_sort(self):
visited = [False] * self.num_vertices
stack = []
for vertex in range(self.num_vertices):
if not visited[vertex]:
self.dfs(vertex, 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)
```
这段代码首先定义了一个有向图的类 `Graph`,其中包含了添加边、深度优先搜索和拓扑排序的方法。在测试示例中,创建了一个有向图实例 `g`,并添加了6个顶点和相应的边。然后调用 `topological_sort` 方法进行拓扑排序,并将结果打印出来。
希望这段代码能够帮助到你理解如何在Python中实现拓扑排序算法。
阅读全文
相关推荐

















