拓扑排序的Kahn算法
**拓扑排序的Kahn算法**
拓扑排序用于对有向无环图(DAG)的节点进行线性排序,使得对于任何有向边 \( u \to v \),节点 \( u \) 都排在节点 \( v \) 之前。Kahn算法是一种基于贪心策略的广度优先方法,其核心思想是不断选择入度为0的节点,并移除其出边,直到所有节点被处理或发现图中存在环。
### 算法步骤详解
1. **初始化入度表**
遍历图中所有节点,统计每个节点的入度(即指向该节点的边数),并记录每个节点的出边(邻接表)。
2025-11-18 06:29:06
0