C++详细讲解图的拓扑排序

什么是拓扑排序

拓扑排序是对于有向无环图(Directed Acyclic Graph)的一种排序，其输出结果为图中每个节点的线性先后序列，满足如果存在一条从节点 A 到节点 B 的路径，则在序列中节点 A 出现在节点 B 的前面。

什么是有向无环图(DAG)

有向无环图是不包含环路并且有一个或多个源点和汇点的有向图。其中源点指没有入度的节点，汇点指没有出度的节点。

如何实现拓扑排序

拓扑排序的实现可以采用拓扑排序算法，一般使用拓扑排序的核心思想，就是去除图中所有的入度为0的节点，再删除这个节点以及所有从这个节点出发的边。重复这个过程，直到找不到入度为0的节点。

代码实现

vector<int> topsort(vector<vector<int>>& graph) 
{
    int n = graph.size(); // n 表示图中点的个数
    vector<int> degree(n, 0); // 存储每个点的入度
    vector<vector<int>> adj(n); // 表示图中每个点的出边

    for (int i = 0; i < n; i++) 
    {
        for (int j = 0; j < graph[i].size(); j++)
        {
            int u = graph[i][j];
            degree[u]++; // 求每个点的入度
            adj[i].push_back(u); // 记录每个点的出边
        }
    }

    queue<int> q; // 用队列保存所有入度为0的节点
    for (int i = 0; i < n; i++) 
    {
        if (degree[i] == 0) q.push(i);
    }

    vector<int> res; // 用来保存最终的结果
    while (!q.empty()) 
    {
        int u = q.front(); q.pop(); // 取出队列的头节点
        res.push_back(u); // 将该节点加入结果中
        for (int i = 0; i < adj[u].size(); i++) 
        {
            int v = adj[u][i];
            degree[v]--; // 删掉该节点相连的出边
            if (degree[v] == 0) q.push(v); // 若该节点入度变为0则入队列
        }
    }

    return res;
}

示例说明

示例1

假设我们要对下面的有向无环图进行拓扑排序：

0 ----> 1 ----> 2 ----> 3
        |              |
        v              v
        4 ----> 5 ----> 6

按照拓扑排序的定义和实现方法，首先需要找到所有入度为0的节点，也就是节点0和节点4，因此将它们入队。

当我们出队节点0时，发现节点1和节点4的入度都会减1，但我们只处理了节点1，因为节点4的入度此时只有1，还不为0，节点4会在以后的队列中被处理。

接着，我们出队节点1，它相连的节点2和5的入度分别减1，这时节点5的入度变为0，被加入队列中，节点2则继续等待。

然后，我们出队节点4，它连接的节点5和6的入度分别减1，节点5和节点6此时的入度都变为0了，它们会被加入到队列中。

接下来出队节点2，使得节点3入度减1，此时节点3的入度变为0，被加入到队列中。最后出队节点5、节点6、节点3，完成了拓扑排序。

示例2

假设还有另外一个有向无环图：

0 ----> 1 ----> 2
        ↑      /
        |    /
        |  /
        ↓
        3

该图的拓扑排序结果是：0 -> 3 -> 1 -> 2。分析一下这个结果的产生，首先将0和3入队，删除它们后，在队列中插入1。此时仅剩节点2的入度不为零，排除2后编号0、3、1、2顺次入队，最终出队即可。

总结

拓扑排序是一种基于有向无环图的排序算法，可以用于解决很多问题。拓扑排序算法的实现中，需要使用队列、入度等数据结构，可以使用C++等高级编程语言轻松实现。