写一个拓扑排序的代码
时间: 2023-07-25 15:04:54 浏览: 42
拓扑排序是一种经典的图论算法,用于解决有向无环图(DAG)的排序问题,其核心思想是通过不断删除入度为0的节点来确定图中节点的线性序列。以下是一个实现拓扑排序的 Python 代码:
```python
from collections import deque
def topological_sort(graph):
# 计算每个节点的入度
in_degree = dict((u, 0) for u in graph)
for u in graph:
for v in graph[u]:
in_degree[v] += 1
# 将入度为0的节点加入队列
queue = deque([u for u in in_degree if in_degree[u] == 0])
# 不断删除入度为0的节点
result = []
while queue:
u = queue.popleft()
result.append(u)
for v in graph[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
# 判断是否存在环
if len(result) != len(graph):
raise ValueError("图中存在环")
return result
```
该算法接受一个字典类型的图作为输入,其中键为节点,值为该节点指向的节点列表。例如,如果存在以下图:
```
A -> B -> C
| ^
v |
D -> E
```
则可以用以下代码表示:
```python
graph = {
'A': ['B', 'D'],
'B': ['C', 'E'],
'D': ['E'],
'E': ['B'],
'C': []
}
```
调用 `topological_sort(graph)` 将返回 `['A', 'D', 'E', 'B', 'C']`,表示该图的一种拓扑排序结果。