【算法学习】拓扑排序（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;elsereturn 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;
}