拓扑排序
拓扑排序是一种针对有向无环图(DAG, Directed Acyclic Graph)的重要算法，常用于处理具有依赖关系的任务调度问题。
基本概念
【定义】拓扑排序是将有向无环图中的所有顶点排成一个线性序列，使得图中任意一对顶点u和v，如果存在一条从u到v的路径，那么在序列中u一定出现在v之前。
关键特性
- 拓扑排序只适用于有向无环图（DAG）
- 如果图中存在环，则无法进行拓扑排序
- 对同一个图，可能存在多个合法的拓扑排序序列
- 拓扑排序可以用来检测图中是否存在环
应用场景
- 任务调度：确定具有依赖关系的任务的执行顺序
- 编译系统：确定程序模块的编译顺序
- 课程安排：根据课程的先修关系安排学习顺序
- 数据处理管道：确定数据流的处理顺序
BFS实现（Kahn算法）
Kahn算法是基于广度优先搜索的拓扑排序算法，其核心思想是不断移除没有入边的节点。
算法步骤
- 计算图中每个顶点的入度
- 将所有入度为0的顶点加入队列
- 取出队列中的一个顶点，将其加入结果序列
- 将该顶点的所有出边删除，更新相邻顶点的入度
- 如果有新的入度为0的顶点，将其加入队列
- 重复步骤3-5，直到队列为空
- 如果结果序列的长度等于图中顶点数，则得到一个拓扑排序；否则，图中存在环，无法进行拓扑排序
代码实现
const int MAXN = 100005;
vector<int> graph[MAXN]; // 邻接表表示的有向图
int inDegree[MAXN]; // 记录每个顶点的入度
vector<int> topologicalOrder; // 存储拓扑排序的结果
// 返回true表示成功找到拓扑排序，false表示图中存在环
bool kahnsAlgorithm(int n) {
// 初始化入度
memset(inDegree, 0, sizeof(inDegree));
// 计算每个顶点的入度
for (int u = 1; u <= n; u++) {
for (int v : graph[u]) {
inDegree[v]++;
}
}
queue<int> q;
// 将所有入度为0的顶点加入队列
for (int i = 1; i <= n; i++) {
if (inDegree[i] == 0) {
q.push(i);
}
}
// 处理队列中的顶点
while (!q.empty()) {
int u = q.front();
q.pop();
topologicalOrder.push_back(u); // 将顶点加入拓扑序列
// 移除所有从u出发的边
for (int v : graph[u]) {
inDegree[v]--;
// 如果v的入度变为0，将其加入队列
if (inDegree[v] == 0) {
q.push(v);
}
}
}
// 检查是否所有顶点都已加入拓扑序列
return topologicalOrder.size() == n;
}
// 打印拓扑排序结果
void printTopologicalOrder() {
for (int vertex : topologicalOrder) {
cout << vertex << " ";
}
cout << endl;
}
时间复杂度分析
- 时间复杂度：O(V+E)，其中V是顶点数，E是边数
- 空间复杂度：O(V)，需要额外的队列和入度数组
DFS实现
也可以使用深度优先搜索实现拓扑排序，其核心思想是在递归调用结束后将顶点加入序列。
算法步骤
- 对图中每个未访问的顶点，开始一次DFS
- 在DFS过程中，递归地访问所有邻接顶点
- 当一个顶点的所有邻接顶点都已被访问，将该顶点加入结果序列的头部
- 最终结果序列即为拓扑排序
代码实现
const int MAXN = 100005;
vector<int> graph[MAXN]; // 邻接表表示的有向图
bool visited[MAXN]; // 记录顶点是否被访问过
bool inStack[MAXN]; // 记录顶点是否在当前DFS路径上（用于检测环）
vector<int> topologicalOrder; // 存储拓扑排序的结果
bool hasCycle; // 标记图中是否存在环
// DFS遍历
void dfs(int u) {
visited[u] = true;
inStack[u] = true; // 标记顶点u在当前DFS路径上
// 访问所有邻接顶点
for (int v : graph[u]) {
if (!visited[v]) {
dfs(v);
} else if (inStack[v]) {
// 如果v已经在当前DFS路径上，说明存在环
hasCycle = true;
return;
}
}
inStack[u] = false; // 顶点u已经处理完毕，移出当前路径
topologicalOrder.push_back(u); // 将顶点加入拓扑序列
}
// 拓扑排序主函数
bool topologicalSort(int n) {
// 初始化
memset(visited, false, sizeof(visited));
memset(inStack, false, sizeof(inStack));
topologicalOrder.clear();
hasCycle = false;
// 对每个未访问的顶点开始DFS
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
dfs(i);
}
}
// 如果存在环，无法进行拓扑排序
if (hasCycle) {
return false;
}
// 由于DFS后加入的顺序与拓扑排序相反，需要反转
reverse(topologicalOrder.begin(), topologicalOrder.end());
return true;
}
时间复杂度分析
- 时间复杂度：O(V+E)
- 空间复杂度：O(V)，需要额外的访问标记数组和调用栈空间
实战应用
判断图中是否存在环
拓扑排序可以用来判断一个有向图是否包含环：
- 如果能够得到一个完整的拓扑排序（排序结果包含所有顶点），则图中不存在环
- 如果无法得到完整的拓扑排序，则图中存在环
求解依赖问题
许多实际问题可以建模为依赖图，然后通过拓扑排序求解：
// 例：课程安排问题
// n个课程，课程编号为1到n
// prerequisites[i] = [a, b]表示课程a依赖于课程b（必须先学习课程b）
bool canFinish(int n, vector<pair<int, int>>& prerequisites) {
// 构建邻接表
vector<int> graph[n+1];
int inDegree[n+1] = {0};
for (const auto& pre : prerequisites) {
int course = pre.first;
int prereq = pre.second;
graph[prereq].push_back(course);
inDegree[course]++;
}
queue<int> q;
int count = 0;
// 将所有入度为0的课程加入队列
for (int i = 1; i <= n; i++) {
if (inDegree[i] == 0) {
q.push(i);
}
}
// 拓扑排序
while (!q.empty()) {
int course = q.front();
q.pop();
count++;
for (int next : graph[course]) {
inDegree[next]--;
if (inDegree[next] == 0) {
q.push(next);
}
}
}
// 如果所有课程都能被选修，则返回true
return count == n;
}
找到所有可能的拓扑排序
在某些情况下，我们可能需要找到所有可能的拓扑排序序列。可以使用回溯法实现：
void allTopologicalSorts(int n, vector<int>& result, bool visited[],
vector<int> graph[], vector<int>& inDegree) {
bool allVisited = true;
// 检查是否所有顶点都已访问
for (int i = 1; i <= n; i++) {
if (!visited[i] && inDegree[i] == 0) {
// 选择当前入度为0的顶点
visited[i] = true;
result.push_back(i);
// 减少邻居的入度
for (int neighbor : graph[i]) {
inDegree[neighbor]--;
}
// 递归查找下一个顶点
allTopologicalSorts(n, result, visited, graph, inDegree);
// 回溯
visited[i] = false;
result.pop_back();
for (int neighbor : graph[i]) {
inDegree[neighbor]++;
}
allVisited = false;
}
}
// 如果所有顶点都已访问，输出当前排序
if (allVisited && result.size() == n) {
printArrangement(result);
}
}
拓扑排序的变种
字典序最小的拓扑排序
有时我们需要找到字典序最小的拓扑排序。只需在BFS实现中使用优先队列代替普通队列：
bool lexicographicalTopSort(int n) {
// 使用优先队列（小顶堆）
priority_queue<int, vector<int>, greater<int>> pq;
// 将所有入度为0的顶点加入队列
for (int i = 1; i <= n; i++) {
if (inDegree[i] == 0) {
pq.push(i);
}
}
// 处理队列中的顶点
while (!pq.empty()) {
int u = pq.top();
pq.pop();
topologicalOrder.push_back(u);
for (int v : graph[u]) {
inDegree[v]--;
if (inDegree[v] == 0) {
pq.push(v);
}
}
}
return topologicalOrder.size() == n;
}
关键路径问题
在带权有向无环图中，关键路径是从源点到汇点的最长路径，常用于项目管理中的关键路径分析(CPM)。可以通过拓扑排序求解：
void criticalPath(int n) {
vector<int> early(n+1, 0); // 最早开始时间
vector<int> late(n+1, INT_MAX); // 最晚开始时间
// 计算最早开始时间（正向拓扑排序）
// ... 拓扑排序代码 ...
// 根据拓扑排序结果计算每个活动的最早开始时间
for (int u : topologicalOrder) {
for (auto& [v, weight] : graph[u]) {
early[v] = max(early[v], early[u] + weight);
}
}
// 初始化汇点的最晚开始时间
int sink = n; // 假设n是汇点
late[sink] = early[sink];
// 计算最晚开始时间（反向拓扑排序）
for (int i = topologicalOrder.size() - 1; i >= 0; i--) {
int u = topologicalOrder[i];
for (auto& [v, weight] : graph[u]) {
late[u] = min(late[u], late[v] - weight);
}
}
// 找出关键活动（最早开始时间等于最晚开始时间的活动）
for (int u = 1; u <= n; u++) {
if (early[u] == late[u]) {
cout << u << " is on the critical path\n";
}
}
}
练习题目推荐
- POJ 1094 Sorting It All Out（拓扑排序基础）
- POJ 1270 Following Orders（输出所有可能的拓扑排序）
- CodeForces 510C Fox And Names（字典序最小的拓扑排序）
- POJ 1128 Frame Stacking（拓扑排序应用）
- UVA 10305 Ordering Tasks（基础拓扑排序题）
总结与技巧
- 检测环：通过拓扑排序可以轻松检测图中是否存在环
- 多源点拓扑排序：对所有入度为0的点同时开始BFS
- 输出所有方案：使用回溯法生成所有可能的拓扑排序
- 优化技巧：
- 使用邻接表而非邻接矩阵表示图
- 预先计算入度，避免重复计算
- 使用优先队列可以获得字典序最小的拓扑排序