概念

拓扑排序是一种可以将有先决条件（即必须将a、b排在前面后再排c，缺一不可）的数据变得有序的一种排序方法。拓扑排序仅可在有向无环图中使用，同时可以判断图中是否有环。因为顺序不同，拓扑排序得到的答案可能不同。

思路

因为排序是有先决条件的，所以可以将要有先决条件的个数（在图中即为入度）记录下来，每满足一个就减一，直到个数为0便可以将其放入序列中。

手动实现

如果我们有如下的一个有向无环图，我们需要对这个图的顶点进行拓扑排序，过程如下：

首先，我们发现V6和v1是没有前驱的，所以我们就随机选去一个输出，我们先输出V6，删除和V6有关的边，得到如下图结果：

然后，我们继续寻找没有前驱的顶点，发现V1没有前驱，所以输出V1，删除和V1有关的边，得到下图的结果：

然后，我们又发现V4和V3都是没有前驱的，那么我们就随机选取一个顶点输出（具体看你实现的算法和图存储结构），我们输出V4，得到如下图结果：

然后，我们输出没有前驱的顶点V3，得到如下结果：

然后，我们分别输出V5和V2，最后全部顶点输出完成，该图的一个拓扑序列为：

v6–>v1—>v4—>v3—>v5—>v2

方法

1.用邻接表存储数据，同时对终点的结点的入度加一；
2.将没有先决条件便可以排序的点（即初始入度为0的点）先加入队列并输出；
3.从队首元素开始扩展，将与队首元素相连的结点的入度减一（等同于擦除这条边），如果该结点入度变为0，则将其入队，作为下一次查找的起点；
4.将队首元素出队，当队首元素为空时停止排序。

代码及注解

有n个点，m条边的有向无环图，输入n，m，然后每一行输入一条边的信息：起点x，终点y

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,c,d,e,re;
struct map1{
    int stat,end;
};
map1 tu[100];
int rd[100],chong[100];
queue <int> q;
int main()
{
    cin>>n>>m;//n点m边
    for (a=1;a<=m;a++)
    {
        cin>>tu[a].stat>>tu[a].end;
        rd[tu[a].end]++;
    }
    for (int i=1;i<=n;i++)
    if (rd[i]==0) q.push(i);//将初始入度为0的结点入队
    while (!q.empty())
    {
            cout<<q.front()<<" ";
            for (int j=1;j<=m;j++)
            {
                if (tu[j].stat==q.front())//找以队首元素为起点的边
                {
                    rd[tu[j].end]--;
                    if (rd[tu[j].end]==0) 
                    {
                        q.push(tu[j].end);
                    }
                }
            }
        q.pop();
    }
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
This work is licensed under a CC BY-NC-SA 4.0 International License.
本文链接：https://llf0703.com/p/topological-sort.html