请编程实现拓扑排序算法
时间: 2023-07-25 15:33:21 浏览: 93
tuopupaixu.rar_随机拓扑
好的,以下是拓扑排序算法的 Python 实现:
```python
from collections import deque
def topological_sort(graph):
"""
拓扑排序算法
:param graph: 以邻接表形式存储的有向图
:return: 拓扑排序结果,如果图中存在环,则返回 None
"""
in_degree = {node: 0 for node in graph} # 记录每个节点的入度
for node in graph:
for neighbor in graph[node]:
in_degree[neighbor] += 1 # 计算每个节点的入度
queue = deque([node for node in graph if in_degree[node] == 0]) # 初始化入度为 0 的节点
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
if len(result) != len(graph):
return None # 存在环,返回 None
else:
return result
```
该算法的时间复杂度为 O(|V| + |E|),其中 |V| 和 |E| 分别是图中的节点数和边数。
阅读全文