拓扑排序(Topological Sorting)是针对有向无环图(DAG, Directed Acyclic Graph)的一种线性排序算法，它使得对于图中的每一条有向边(u→v)，顶点u在排序中都出现在顶点v之前。
一、核心概念与性质
- 基本定义：
• 对有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列
• 若存在边u→v，则u在序列中必须出现在v之前 - 关键性质：
• 无环性：仅适用于DAG，若图中存在环则无法进行拓扑排序
• 不唯一性：同一DAG可能有多种合法的拓扑排序结果
• 偏序到全序：将图中的偏序关系转化为全序关系 - 应用场景：
• 任务调度（项目管理中的任务依赖关系）
• 课程安排（先修课程要求）
• 编译顺序（源文件依赖关系）
• 电路设计（元件布线顺序）
• 生产调度（零部件生产顺序）
二、算法实现
1. Kahn算法（基于入度）
算法步骤：
- 计算所有节点的入度（指向该节点的边数）
- 将入度为0的节点加入队列
- 从队列中取出节点并加入结果序列
- 将该节点的所有邻接节点入度减1
- 若邻接节点入度变为0，则加入队列
- 重复直到队列为空
- 若结果节点数≠总节点数，说明有环
C++实现：
bool topologicalSort(vector<vector<int>>& G, vector<int>& inDegree, int n) {
queue<int> q;
vector<int> res;
for(int i=0; i<n; i++)
if(inDegree[i] == 0) q.push(i);
while(!q.empty()) {
int u = q.front(); q.pop();
res.push_back(u);
for(int v : G[u]) {
if(--inDegree[v] == 0)
q.push(v);
}
}
return res.size() == n;
}
2. DFS算法
算法步骤：
- 对未访问节点进行DFS
- 递归访问所有邻接节点
- 递归完成后将当前节点压入栈
- 最终栈的逆序即为拓扑排序
Python实现：
def topological_sort_dfs(graph):
visited = set()
stack = []
def dfs(u):
visited.add(u)
for v in graph.get(u, []):
if v not in visited:
dfs(v)
stack.append(u)
for u in graph:
if u not in visited:
dfs(u)
return stack[::-1]
三、复杂度分析
| 算法 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| Kahn | O(V+E) | O(V) | 易于理解，适合动态图 |
| DFS | O(V+E) | O(V) | 代码简洁，需要递归 |
四、实际应用示例
课程安排问题（LeetCode 207）
问题：判断能否完成所有课程（无环则可完成）
Java解法：
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<Integer>[] graph = new List[numCourses];
int[] inDegree = new int[numCourses];
for(int i=0; i<numCourses; i++)
graph[i] = new ArrayList<>();
for(int[] cp : prerequisites) {
graph[cp[1]].add(cp[0]);
inDegree[cp[0]]++;
}
Queue<Integer> q = new LinkedList<>();
for(int i=0; i<numCourses; i++)
if(inDegree[i] == 0) q.offer(i);
int count = 0;
while(!q.isEmpty()) {
int pre = q.poll();
count++;
for(int cur : graph[pre])
if(--inDegree[cur] == 0)
q.offer(cur);
}
return count == numCourses;
}
五、常见问题与技巧
- 环检测：若拓扑排序结果节点数少于总节点数，说明图中存在环
- 并行任务：同一层级入度为0的节点可并行处理
- 字典序排序：使用优先队列代替普通队列可获得字典序最小的排序
- 动态图处理：Kahn算法更适合动态变化的图结构
