拓扑排序：任务调度背后的逻辑

百里宵月 · 昨天 19:52

引言

在图论中，拓扑排序（Topological Sorting）是一种重要的算法，主要用于解决有向无环图（DAG）中的依赖关系问题。它在任务调度、编译器的依赖解析、课程安排等领域有着广泛的应用。本文将详细介绍拓扑排序的背景、定义、原理、应用场景，并通过伪代码和具体代码实现帮助读者深入理解。最后，我们将结合一道题目，讲解如何使用拓扑排序解决实际问题。
背景知识

有向无环图（DAG）

有向图：由顶点和有向边组成的图，边具有方向性。
无环图：图中不存在任何有向环路。
拓扑排序：只适用于有向无环图（DAG），用于确定顶点的线性顺序，使得对于每一条有向边 $(u, v)$，顶点 $u$ 在顶点 $v$ 之前。

拓扑排序的应用场景

任务调度：确定任务的执行顺序，确保依赖任务先完成。
编译器：解析源代码中的依赖关系，确定编译顺序。
课程安排：确定课程的选修顺序，确保先修课程在前。
项目管理：确定任务的优先级和顺序。

拓扑排序的定义

给定一个有向无环图 $G = (V, E)$，拓扑排序是将图中所有顶点排成一个线性序列，使得对于每一条有向边 $(u, v)$，顶点 $u$ 在顶点 $v$ 之前。
示例

假设有以下有向图：

1 -> 2 -> 3
1 -> 4
4 -> 3

复制代码

一个合法的拓扑排序是：1, 2, 4, 3 或 1, 4, 2, 3。
拓扑排序的原理

拓扑排序的核心思想是通过不断移除入度为 0 的顶点，并更新其邻接顶点的入度，直到所有顶点都被移除或无法继续移除。
算法步骤

初始化：
- 计算每个顶点的入度（即指向该顶点的边的数量）。
- 将所有入度为 0 的顶点加入队列。
处理队列：
- 从队列中取出一个顶点，将其加入拓扑排序结果。
- 遍历该顶点的所有邻接顶点，将其入度减 1。如果某个邻接顶点的入度变为 0，则将其加入队列。
结束条件：
- 如果所有顶点都被处理，则拓扑排序成功。
- 如果队列为空但仍有未处理的顶点，则图中存在环，拓扑排序失败。

拓扑排序的伪代码

function TopologicalSort(Graph):
// 初始化
in_degree = 计算每个顶点的入度
queue = 所有入度为 0 的顶点
result = 空列表
// 处理队列
while queue 不为空:
u = queue.pop()
result.append(u)
for each v in u 的邻接顶点:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.push(v)
// 检查是否所有顶点都被处理
if result 的长度等于图的顶点数:
return result
else:
return "图中存在环，无法进行拓扑排序"

复制代码

拓扑排序的代码实现

示例1

ACWing 有向图的拓扑序列
以下是拓扑排序的 C++ 实现，结合题目要求输出任意一个合法的拓扑序列，如果不存在则输出 -1。

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int maxn = 1e5 + 7; // 定义最大顶点数和边数
int n, m; // 顶点数和边数
int in[maxn]; // 存储每个顶点的入度
int h[maxn], ne[maxn], t[maxn], idx; // 邻接表存储图
// 添加一条有向边
void add(int u, int v) {
ne[++idx] = h[u];
h[u] = idx;
t[idx] = v;
}
// 拓扑排序函数
void topo() {
int cnt = 0; // 记录已处理的顶点数
queue<int> q, ans; // q 用于 BFS，ans 用于存储拓扑排序结果
// 将所有入度为 0 的顶点加入队列
for (int i = 1; i <= n; i++) {
if (!in[i]) {
q.push(i);
cnt++;
ans.push(i);
}
}
// BFS 遍历
while (!q.empty()) {
int cur = q.front();
q.pop();
// 遍历当前顶点的所有邻接顶点
for (int i = h[cur]; i != -1; i = ne[i]) {
int v = t[i];
in[v]--; // 邻接顶点的入度减 1
if (!in[v]) { // 如果入度为 0，加入队列
q.push(v);
cnt++;
ans.push(v);
}
}
}
// 判断是否所有顶点都被处理
if (cnt != n) {
cout << -1; // 存在环，无法进行拓扑排序
} else {
// 输出拓扑排序结果
while (!ans.empty()) {
cout << ans.front() << " ";
ans.pop();
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m; // 输入顶点数和边数
memset(h, -1, sizeof(h)); // 初始化邻接表
// 输入 m 条边
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
in[y]++; // 更新入度
add(x, y); // 添加有向边
}
topo(); // 调用拓扑排序函数
return 0;
}

复制代码

代码解析

1. 数据结构

邻接表：使用数组 h、ne 和 t 存储图。
入度数组：in 表示顶点 $i$ 的入度。
队列：用于 BFS 遍历和存储拓扑排序结果。

2. 拓扑排序函数

初始化：将所有入度为 0 的顶点加入队列。

BFS 遍历：从队列中取出顶点，更新其邻接顶点的入度，并将入度为 0 的顶点加入队列。

结果输出：如果所有顶点都被处理，则输出拓扑排序结果；否则输出 -1。

3. 主函数

输入处理：读取顶点数、边数以及边的信息，并初始化邻接表和入度数组。

调用拓扑排序：执行拓扑排序并输出结果。

复杂度分析

时间复杂度

初始化：$O(n + m)$，其中 $n$ 是顶点数，$m$ 是边数。

BFS 遍历：$O(n + m)$。

空间复杂度

邻接表：$O(m)$。

队列和入度数组：$O(n)$。

示例2

洛谷杂物
题目描述

John 的农场有 ( n ) 个杂务需要完成，每个杂务需要一定的时间，并且某些杂务必须在其他杂务完成后才能开始。我们需要计算完成所有杂务所需的最短时间。
输入格式

第 1 行：一个整数 ( n )，表示杂务的数量。

第 2 到 ( n+1 ) 行：每行包含杂务的编号、完成时间以及其依赖的杂务列表（以 0 结束）。

输出格式

一个整数，表示完成所有杂务所需的最短时间。

样例输入 #1

7
1 5 0
2 2 1 0
3 3 2 0
4 6 1 0
5 1 2 4 0
6 8 2 4 0
7 4 3 5 6 0
复制代码
样例输出 #1

23
复制代码
解题思路

1. 问题分析

每个杂务可以看作图中的一个顶点。

杂务之间的依赖关系可以看作有向边。

我们需要找到一种顺序，使得所有杂务都能在其依赖的杂务完成后开始，并且总时间最短。

2. 拓扑排序的应用

拓扑排序可以用于解决有向无环图（DAG）中的依赖关系问题。

通过拓扑排序，我们可以确定杂务的执行顺序，并计算完成所有杂务的最短时间。

3. 算法设计

构建图：

使用邻接表存储杂务之间的依赖关系。

记录每个杂务的入度（即依赖的杂务数量）。

拓扑排序：

使用优先队列（堆）选择当前可以执行的杂务（入度为 0）。

更新杂务的完成时间，并将其依赖的杂务的入度减 1。

计算最短时间：

在拓扑排序过程中，记录每个杂务的完成时间，并更新全局的最短时间。

在本题中，我们设计利用一个优先队列，保证当前任务耗时最长的依赖任务在最后出队，这样才能保证时间更新的正确性。

我们结合示例进行分析：
7
1 5 0
2 2 1 0
3 3 2 0
4 6 1 0
5 1 2 4 0
6 8 2 4 0
7 4 3 5 6 0
复制代码

代码实现

以下是结合拓扑排序的 C++ 实现：
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int maxn = 1e4 + 7; // 定义最大杂务数
int n; // 杂务数量
int in[maxn]; // 存储每个杂务的入度
int times[maxn]; // 存储每个杂务的完成时间
int h[maxn * 100], ne[maxn * 100], t[maxn * 100], idx; // 邻接表存储图
// 添加一条有向边
void add(int u, int v) {
ne[++idx] = h[u];
h[u] = idx;
t[idx] = v;
}
// 拓扑排序函数
void topo() {
int mx = 0; // 记录全局的最短时间
priority_queue<pair<int, int>> q; // 优先队列，存储 (负完成时间, 杂务编号)

// 将所有入度为 0 的杂务加入队列
for (int i = 1; i <= n; i++) {
      if (!in[i]) {
         q.push({-times[i], i});
      }
}
// BFS 遍历
while (!q.empty()) {
      auto cur = q.top();
      q.pop();
      int cur_time = -cur.first; // 当前杂务的完成时间
      int u = cur.second; // 当前杂务的编号
//最短完成时间但是取max的原因是需要等待耗时最长的依赖完成才能开始任务
      mx = max(mx, cur_time); // 更新全局的最短时间
      // 遍历当前杂务的所有依赖杂务
      for (int i = h[u]; i != -1; i = ne[i]) {
         int v = t[i];
         in[v]--; // 依赖杂务的入度减 1
         if (!in[v]) {
            // 如果依赖杂务的入度为 0，将其加入队列
            q.push({-(cur_time + times[v]), v});
         }
      }
}
// 输出全局的最短时间
cout << mx;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n; // 输入杂务数量
memset(h, -1, sizeof(h)); // 初始化邻接表
// 输入每个杂务的信息
for (int i = 1; i <= n; i++) {
      int id;
      cin >> id;
      cin >> times[id]; // 输入杂务的完成时间
      int pre;
      cin >> pre;
      while (pre) {
         in[id]++; // 更新杂务的入度
         add(pre, id); // 添加依赖关系
         cin >> pre;
      }
}
topo(); // 调用拓扑排序函数
return 0;
}
复制代码
代码解析

1. 数据结构

邻接表：使用数组 h、ne 和 t 存储杂务之间的依赖关系。

入度数组：in 表示杂务 ( i ) 的入度（即依赖的杂务数量）。

完成时间数组：times 表示杂务 ( i ) 的完成时间。

优先队列：用于选择当前可以执行的杂务。

2. 拓扑排序函数

初始化：将所有入度为 0 的杂务加入优先队列。

BFS 遍历：

从队列中取出杂务，更新其完成时间。

遍历其依赖的杂务，更新其入度。

如果某个依赖杂务的入度为 0，则将其加入队列。

结果输出：输出全局的最短时间。

3. 主函数

输入处理：读取杂务数量、完成时间以及依赖关系，并初始化邻接表和入度数组。

调用拓扑排序：执行拓扑排序并输出结果。

总结

拓扑排序是解决有向无环图中依赖关系问题的有效算法。通过本文的介绍，读者可以掌握拓扑排序的定义、原理、实现方法以及应用场景。结合代码实现和题目讲解，希望读者能够深入理解拓扑排序，并在实际问题中灵活运用。
如果你对拓扑排序或其他图论算法有更多疑问，欢迎在评论区留言讨论！

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

账号		自动登录	找回密码
密码			立即注册