【算法学习】拓扑排序（Topological Sorting)
目录
定义
例子
拓扑排序的实现
核心思想
实现方法
1，Kahn算法（基于贪心策略）
步骤：
用二维数组存储图的例子
用哈希表存储图的例子
2，基于DFS的后序遍历法
总结
拓扑排序的应用场景
1，任务调度
2，课程安排
3，编译器优化
4，数据库查询优化
定义
拓扑排序是针对 有向无环图(DAG,Directed Acyclic Graph)的一种线性排序的算法。使得对于图中的每一条有向边u->v，节点u在排序中都出现在节点v之前。
例子
对于这个有向无环图，边有1->2，2->3，1->4，4->5，2->3。那么在拓扑排序中，1一定出现在2的前面，2一定出现在3的前面......。
拓扑排序的过程：每次选数时，都选择图中入度为0的节点，然后遍历该节点所连接的节点，将它们的入度减一，重复该过程，直到排序结果中包含所有节点，排序完成。
- 如果图中存在环，比如1->2，2->3，3->1。在该图中没有入度为0的节点，无法选数。
- 所以拓扑排序有一个重要的应用，判断有向图是否带环，如果不带环，则排序结果包含所有的节点；反之，该图带环。
拓扑排序的结果有这几种可能：
- 1 2 3 4 5
- 1 4 2 3 5
- 1 4 2 5 3
- 1 2 4 5 3
- 1 2 4 3 5
可以发现，拓扑排序的结果不是唯一的。
拓扑排序的实现
对拓扑排序可以总结如下：
核心思想
目标：将图中的节点按依赖关系线性化，确保所有前驱节点优先于后继节点。
适用条件：仅适用于无环的有向图（若图中有环，则无法完成拓扑排序）。
实现方法
1，Kahn算法（基于贪心策略）
该算法也就是图中的广度优先搜索（BFS）算法。
步骤：
1，初始化
- 统计图中所有节点的入度。
- 将入度为0的节点加入队列中。
2，循环处理
- 取出队列中的结果u，加入到排序结果中。
- 遍历u所指向的节点v，将v的入度减1。
- 若v的入度变为0，将v加入队列中。
3，终止条件
- 若排序结果包含所有节点 ->成功
- 若仍有节点未处理且队列为空 ->失败，图中有环
还有一个问题，就是如何来表示图，或者是存储图。我们可以用STL中的容器来抽象表示：
vector<vector<int>> 二维数组和unordered_map<int,vector<int>> 哈希表。这两种都可以用来存储int类型的，但如果节点是string类型的（如节点表示课程名称），使用unordered_map<string,vector<string>> 存图。
用二维数组存储图的例子
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
bool TopSort(vector<vector<int>>& graph, int n, vector<int>& inDgree)
{
int num = 0; //统计排序结果的数目
queue<int> q;
for (int i = 0; i < n; i++) //将所有入度为0的节点放入队列中
{
if (inDgree[i] == 0)
q.push(i);
}
while (q.size()) //循环处理
{
int u = q.front(); //取队首
q.pop();
cout << u << " ";
for (int v : graph[u]) //u->v
{
inDgree[v]--; //节点v入度减一
if (inDgree[v] == 0) //节点v入度为0则入队列
q.push(v);
}
num++;
}
cout << endl;
if (num == n)
return true;
else
return false;
}
int main()
{
int n, m;
cout << "请输入顶点数和边数:";
cin >> n >> m;
vector<vector<int>> G(n); //二维数组模拟邻接表存图
for (int i = 0; i < m; i++)
{
int x, y;
cout << "请输入第" << i + 1 << "条边:" ;
cin >> x >> y;
G[x].push_back(y);
}
vector<int> inDgree(n); //记录入度
for (auto x : G)
{
for (int y : x) //节点指向 x->y
{
inDgree[y]++; //y的入度++
}
}
cout << "拓扑排序结果为:";
bool ret = TopSort(G, n, inDgree);
cout << ret << endl;
return 0;
}
用哈希表存储图的例子
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
vector<string> TopSort(unordered_map<string, vector<string>>& graph)
{
unordered_map<string, int> inDgree; //记录入度
queue<string> q;
vector<string> result; //排序结果
for (auto& [u,neighbors] : graph) //初始化入度
{
if (!inDgree.count(u)) inDgree[u] = 0; //确保所有节点被记录
for (string v : neighbors)
{
inDgree[v]++;
}
}
for (auto& [node,degree] : inDgree) //入度为0的入队列
{
if (degree == 0)
{
q.push(node);
}
}
//处理队列
while (q.size())
{
string u = q.front();
q.pop();
result.push_back(u);
for (auto& v : graph[u]) //u->v
{
inDgree[v]--; //入度--
if (inDgree[v] == 0)
{
q.push(v); //入度为0，入队列
}
}
}
//检查环
if (result.size() != inDgree.size())
return {};
return result;
}
int main()
{
//课程依赖关系 (u->v)表示u是v的先修课
unordered_map<string, vector<string>> graph = {
{"C1",{"C2","C3"}},
{"C2",{"C4"}},
{"C3",{"C4"}},
{"C4",{}},
{"C5",{"C4"}}
};
//拓扑排序
vector<string> order = TopSort(graph);
if (order.empty())
cout << "图中存在环!" << endl;
else
{
cout << "拓扑排序结果为:";
for (string node : order)
{
cout << node << " ";
}
}
return 0;
}
2，基于DFS的后序遍历法
步骤：
对每个未访问的节点执行DFS。
递归访问所有邻接节点。
将当前节点加入栈。
最终反转结果得到拓扑排序。
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <string>
using namespace std;
bool dfs(const string& u,
unordered_map<string, vector<string>>& graph,
unordered_set<string>& visited,
unordered_set<string>& inStack,
vector<string>& result)
{
//该节点在访问路径中出现过，说明存在环
if (inStack.count(u)) return false;
//该节点已处理过，不再处理
if (visited.count(u)) return true;
inStack.insert(u);
visited.insert(u);
for (string v : graph[u])
{
if (!dfs(v, graph, visited, inStack, result))
return false;
}
inStack.erase(u);
result.push_back(u);
return true;
}
vector<string> TopSort(unordered_map<string, vector<string>>& graph)
{
vector<string> result; //记录结果
unordered_set<string> inStack; //记录访问路径 ，如果重复出现，说明存在环
unordered_set<string> visited; //记录访问过的节点
for (auto& [u, _] : graph)
{
if (!visited.count(u))
{
if (!dfs(u, graph, visited, inStack, result))
return {}; //存在环
}
}
return result;
}
int main()
{
//课程依赖关系 (u->v)表示u是v的先修课
unordered_map<string, vector<string>> graph = {
{"C1",{"C2","C3"}},
{"C2",{"C4"}},
{"C3",{"C4"}},
{"C4",{}},
{"C5",{"C4"}}
};
//拓扑排序
vector<string> order = TopSort(graph);
reverse(order.begin(), order.end());
if (order.empty())
cout << "图中存在环!" << endl;
else
{
cout << "拓扑排序结果为:";
for (string node : order)
{
cout << node << " ";
}
}
return 0;
} 
总结
- 两种算法均能高效实现拓扑排序，时间复杂度均为O(V+E)，V为顶点数，E为边数。
- 若节点类型为int，可将unordered_map替换为vector提升性能。
拓扑排序的应用场景
1，任务调度
在项目管理中，任务之间可能存在依赖关系，某些任务必须在其他任务完成之后才能开始。通过拓扑排序，可以确定任务的执行顺序，确保每个任务在开始之前其前置任务已经完成。
2，课程安排
在教育领域，某些课程可能需要先修其他课程。通过拓扑排序，可以确定合理的课程修读顺序，避免循环依赖，帮助学生按照逻辑顺序学习课程内容。
3，编译器优化
在编译过程中，源代码的不同模块之间可能存在依赖关系。拓扑排序可以帮助确定模块的编译顺序，确保每个模块在被调用之前已经被正确编译。（如Makefile）
4，数据库查询优化
在数据库设计中，表与表之间可能存在外键约束。通过拓扑排序，可以决定表的插入或删除顺序，以避免违反外键约束。