当前位置：首页 > 文章列表 > 文章 > python教程 > Python拓扑排序使用方法详解

Python拓扑排序使用方法详解

2026-01-12 14:35:40 0浏览收藏

小伙伴们对文章编程感兴趣吗？是否正在学习相关知识点？如果是，那么本文《Python拓扑排序怎么用？》，就很适合你，本篇文章讲解的知识点主要包括。在之后的文章中也会多多分享相关知识点，希望对大家的知识积累有所帮助！

拓扑排序用于有向无环图，通过Kahn算法实现：先统计入度，将入度为0的节点入队，依次处理节点并更新邻居入度，最终得到线性序列；若结果包含所有节点则排序成功，否则存在环。

python中拓扑排序如何使用？

拓扑排序用于有向无环图（DAG），可以找出节点的线性顺序，使得对于每一条有向边 (u, v)，u 在排序中都出现在 v 的前面。Python 中可以通过 BFS（广度优先搜索）结合入度表来实现，常用于任务调度、依赖关系处理等场景。

拓扑排序的基本思路

使用 Kahn 算法进行拓扑排序：

统计每个节点的入度（有多少条边指向它）
将所有入度为 0 的节点加入队列
依次从队列中取出节点，将其邻居的入度减一
如果邻居入度变为 0，加入队列
记录取出节点的顺序，即为拓扑序

Python 实现示例

from collections import deque, defaultdict
def topological_sort(edges, n):
建图并统计入度
graph = defaultdict(list)
indegree = [0] * n

for u, v in edges:
    graph[u].append(v)
    indegree[v] += 1

# 找出入度为 0 的节点
queue = deque([i for i in range(n) if indegree[i] == 0])
result = []

while queue:
    node = queue.popleft()
    result.append(node)

    for neighbor in graph[node]:
        indegree[neighbor] -= 1
        if indegree[neighbor] == 0:
            queue.append(neighbor)

# 如果结果长度等于节点数，说明无环
if len(result) == n:
    return result
else:
    return []  # 存在环，无法拓扑排序
示例：4 个任务，边表示依赖关系
edges = [(0, 1), (0, 2), (1, 2), (2, 3)]
n = 4
order = topological_sort(edges, n)
print("拓扑排序结果:", order)  # 输出: [0, 1, 2, 3]