拓扑排序：任务调度背后的逻辑
引言在图论中，拓扑排序（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 -= 1
if in_degree == 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; // 存储每个顶点的入度
int h, ne, t, idx; // 邻接表存储图
// 添加一条有向边
void add(int u, int v) {
ne[++idx] = h;
h = idx;
t = v;
}
// 拓扑排序函数
void topo() {
int cnt = 0; // 记录已处理的顶点数
queue<int> q, ans; // q 用于 BFS，ans 用于存储拓扑排序结果
// 将所有入度为 0 的顶点加入队列
for (int i = 1; i <= n; i++) {
if (!in) {
q.push(i);
cnt++;
ans.push(i);
}
}
// BFS 遍历
while (!q.empty()) {
int cur = q.front();
q.pop();
// 遍历当前顶点的所有邻接顶点
for (int i = h; i != -1; i = ne) {
int v = t;
in--; // 邻接顶点的入度减 1
if (!in) { // 如果入度为 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++; // 更新入度
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; // 存储每个杂务的入度
int times; // 存储每个杂务的完成时间
int h, ne, t, idx; // 邻接表存储图
// 添加一条有向边
void add(int u, int v) {
ne[++idx] = h;
h = idx;
t = v;
}
// 拓扑排序函数
void topo() {
int mx = 0; // 记录全局的最短时间
priority_queue<pair<int, int>> q; // 优先队列，存储 (负完成时间, 杂务编号)
// 将所有入度为 0 的杂务加入队列
for (int i = 1; i <= n; i++) {
if (!in) {
q.push({-times, 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; i != -1; i = ne) {
int v = t;
in--; // 依赖杂务的入度减 1
if (!in) {
// 如果依赖杂务的入度为 0，将其加入队列
q.push({-(cur_time + times), 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; // 输入杂务的完成时间
int pre;
cin >> pre;
while (pre) {
in++; // 更新杂务的入度
add(pre, id); // 添加依赖关系
cin >> pre;
}
}
topo(); // 调用拓扑排序函数
return 0;
}代码解析
1. 数据结构
[*]邻接表：使用数组 h、ne 和 t 存储杂务之间的依赖关系。
[*]入度数组：in 表示杂务 ( i ) 的入度（即依赖的杂务数量）。
[*]完成时间数组：times 表示杂务 ( i ) 的完成时间。
[*]优先队列：用于选择当前可以执行的杂务。
2. 拓扑排序函数
[*]初始化：将所有入度为 0 的杂务加入优先队列。
[*]BFS 遍历：
[*]从队列中取出杂务，更新其完成时间。
[*]遍历其依赖的杂务，更新其入度。
[*]如果某个依赖杂务的入度为 0，则将其加入队列。
[*]结果输出：输出全局的最短时间。
3. 主函数
[*]输入处理：读取杂务数量、完成时间以及依赖关系，并初始化邻接表和入度数组。
[*]调用拓扑排序：执行拓扑排序并输出结果。
总结
拓扑排序是解决有向无环图中依赖关系问题的有效算法。通过本文的介绍，读者可以掌握拓扑排序的定义、原理、实现方法以及应用场景。结合代码实现和题目讲解，希望读者能够深入理解拓扑排序，并在实际问题中灵活运用。
如果你对拓扑排序或其他图论算法有更多疑问，欢迎在评论区留言讨论！
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]