写一道拓普排序的代码并加注释
时间: 2023-05-24 19:06:18 浏览: 102
拓扑排序(Topological Sorting)是一种有向无环图(DAG, Directed Acyclic Graph)的排序算法。
拓扑排序有两种实现方式,一种是基于DFS(深度优先遍历),一种是基于BFS(广度优先遍历)。这里我们介绍基于BFS的拓扑排序算法。
算法步骤:
1. 统计每个节点的入度,初始化队列将所有入度为0的节点入队。
2. 当队列非空时,取出队首节点,遍历其所有后继节点,在后继节点的入度表中将其入度减1。
3. 如果某个后继节点入度减为0,将其入队。
4. 如果队列为空时,还有节点的入度不为0,则证明图中存在环。
代码实现:
```python
from collections import deque
def topological_sort(graph):
# 统计每个节点的入度
in_degree = {u: 0 for u in graph}
for u in graph:
for v in graph[u]:
in_degree[v] += 1
# 将所有入度为0的节点加入队列
q = deque([u for u in in_degree if in_degree[u] == 0])
result = []
while q:
u = q.popleft()
result.append(u)
# 遍历所有后继节点,将其入度减1
for v in graph[u]:
in_degree[v] -= 1
# 如果某个后继节点入度减为0,将其入队
if in_degree[v] == 0:
q.append(v)
# 如果结果集中的节点数小于图中的节点数,则证明图中存在环
if len(result) < len(graph):
return None
return result
```
注:该代码中的 graph 是一个字典,表示图中每个节点所拥有的后继节点。例如:graph = {0: [1, 2], 1: [3], 2: [3], 3: []} 表示有4个节点,0号节点后继有1号和2号节点,1号和2号节点后继有3号节点,3号节点没有后继。
阅读全文