拓扑优化99行python代码
栏目:公司新闻 发布时间:2024-09-09
当然,我可以帮你优化一下拓扑排序的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 是边的数量。希望这个优化的代码能够满足你的需求!如果你有其他问题,请随时问我。

平台注册入口