拓扑排序算法详解：定义、实现与应用场景

拓扑排序算法详解：定义、实现与应用场景

引用

CSDN

1.

https://m.blog.csdn.net/2401_82677021/article/details/145566900

拓扑排序是图论中的一个重要算法，主要用于处理有向无环图（DAG）的线性排序问题。它在任务调度、课程安排、编译器优化等多个领域都有广泛的应用。本文将详细介绍拓扑排序的定义、实现方法以及应用场景，帮助读者全面理解这一算法。

定义

拓扑排序是针对有向无环图（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> 二维数组
• unordered_map<int,vector> 哈希表
• 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的后序遍历法

步骤：

1. 对每个未访问的节点执行DFS。
2. 递归访问所有邻接节点。
3. 将当前节点加入栈。
4. 最终反转结果得到拓扑排序。

#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. 数据库查询优化

在数据库设计中，表与表之间可能存在外键约束。通过拓扑排序，可以决定表的插入或删除顺序，以避免违反外键约束。