100种算法【Python版】第40篇——卡恩算法
本文目录
- 1 算法说明
- 2 算法示例：任务调度
- 3 算法应用：软件项目构建
1 算法说明
卡恩算法由 Arthur Kahn 于 1962 年首次提出，用于对有向无环图（DAG）进行拓扑排序。这种算法通过逐步消除入度为零的节点来实现排序，适用于解决具有依赖关系的任务调度问题。
算法核心
- 入度概念：节点的入度是指向该节点的边的数量。入度为零的节点没有依赖，可以立即执行。
- 迭代消除：从入度为零的节点开始，依次移除节点并减少其邻接节点的入度。这种迭代消除的过程确保了每个节点在其所有前驱节点处理完后再处理。
算法的实现步骤
（1）计算入度：
- 初始化每个节点的入度为零。
- 遍历图中的每条边，计算目标节点的入度。
（2）初始化队列：
- 将所有入度为零的节点加入队列，表示这些节点可以立即处理。
（3）处理队列：
- 依次从队列中取出节点，将其加入拓扑排序结果。
- 遍历该节点的每个邻接节点，将其入度减一。
- 如果某个邻接节点的入度减为零