python优序图法
时间: 2023-12-27 22:25:08 浏览: 32
优序图法是一种常见的排序算法,它可以对一个无向图进行拓扑排序。拓扑排序是指将有向无环图(DAG)中的节点按照一定的顺序进行排序的过程。在优序图法中,首先找到图中没有前驱节点的节点,将其加入结果列表中,并将其从图中删除。然后继续找到新的没有前驱节点的节点,重复上述过程,直到所有节点都被加入结果列表中。
以下是用Python实现优序图法的代码示例:
```python
def topologicalSort(graph):
# 计算每个节点的入度
in_degree = {node: 0 for node in graph}
for node in graph:
for neighbor in graph[node]:
in_degree[neighbor] += 1
# 找到没有前驱节点的节点
queue = [node for node in graph if in_degree[node] == 0]
# 拓扑排序结果列表
result = []
# 依次处理节点
while queue:
node = queue.pop(0)
result.append(node)
# 更新入度
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return result
```
使用示例:
```python
graph = {
'A': ['B', 'C'],
'B': ['D'],
'C': ['D'],
'D': []
}
sorted_nodes = topologicalSort(graph)
print(sorted_nodes) # 输出:['A', 'C', 'B', 'D']
```