给我一个拓扑排序的代码
时间: 2024-05-08 07:17:58 浏览: 44
拓扑排序代码
Sure, here's a sample code for topological sorting in Python:
```
from collections import deque
def topological_sort(graph):
# Create a dictionary to store the in-degrees of each vertex
in_degree = {node: 0 for node in graph}
# Calculate the in-degrees of each vertex
for node in graph:
for neighbor in graph[node]:
in_degree[neighbor] += 1
# Create a queue to store the nodes with zero in-degree
zero_in_degree_nodes = deque([node for node in in_degree if in_degree[node] == 0])
# Perform topological sort
sorted_nodes = []
while zero_in_degree_nodes:
node = zero_in_degree_nodes.popleft()
sorted_nodes.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
zero_in_degree_nodes.append(neighbor)
# Check for cycles
if len(sorted_nodes) != len(graph):
raise ValueError("Graph has a cycle")
return sorted_nodes
```
Hope this helps!
阅读全文