当然,我可以帮你优化一下拓扑排序的Python代码。以下是一个基本的拓扑排序实现,使用邻接表来表示图:```pythonfromcollectionsimportdefaultdictdeftopological_sort(graph):#计算每个节点的入度in_degr
当然,我可以帮你优化一下拓扑排序的 Python 代码。以下是一个基本的拓扑排序实现,使用邻接表来表示图:
```python
from collections import defaultdict
def topological_sort(graph):
# 计算每个节点的入度
in_degree=defaultdict(int)
for node in graph:
for neighbor in graph[node]:
in_degree[neighbor] +=1
# 找到入度为 0 的节点作为起始点
start_nodes=[node for node in graph if in_degree[node]==0]
# 开始拓扑排序
sorted_nodes=[]
while start_nodes:
node=start_nodes.pop(0)
sorted_nodes.append(node)
# 更新相邻节点的入度
for neighbor in graph[node]:
in_degree[neighbor] -=1
if in_degree[neighbor]==0:
start_nodes.append(neighbor)
# 检查是否有环
if len(sorted_nodes) !=len(graph):
raise ValueError("图中存在环")
return sorted_nodes
# 测试
graph={
'A': ['B', 'C'],
'B': ['D'],
'C': ['D', 'E'],
'D': ['E'],
'E': []
}
sorted_nodes=topological_sort(graph)
print(sorted_nodes)
```
这段代码使用了拓扑排序的经典算法,时间复杂度为 O(V + E),其中 V 是节点数量,E 是边的数量。希望这个优化的代码能够满足你的需求!如果你有其他问题,请随时问我。