拓扑排序用于有向无环图，通过Kahn算法实现：先统计入度，将入度为0的节点入队，依次处理节点并更新邻居入度，最终得到线性序列；若结果包含所有节点则排序成功，否则存在环。
拓扑排序用于有向无环图（DAG），可以找出节点的线性顺序，使得对于每一条有向边 (u, v)，u 在排序中都出现在 v 的前面。Python 中可以通过 BFS（广度优先搜索）结合入度表来实现，常用于任务调度、依赖关系处理等场景。
拓扑排序的基本思路
使用 Kahn 算法进行拓扑排序：
- 统计每个节点的入度（有多少条边指向它）
- 将所有入度为 0 的节点加入队列
- 依次从队列中取出节点，将其邻居的入度减一
- 如果邻居入度变为 0，加入队列
- 记录取出节点的顺序，即为拓扑序
Python 实现示例
from collections import deque, defaultdictdef topolog
ical_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]
ical_sort(edges, n):常见用途和注意事项
拓扑排序适用于：
- 课程学习顺序（先修课）
- 编译任务执行顺序
- 包依赖安装
注意点：
- 图必须是有向无环图，否则无解
- 多个合法拓扑序可能同时存在，算法输出的是其中一种
- 节点编号建议从 0 开始连续，或使用字典映射处理非连续编号
基本上就这些，掌握建图、入度统计和队列处理就能应对大多数场景。
