拓扑排序

冷不防 2022-06-09 05:57 215阅读 0赞

# 什么是拓扑排序? #

在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：

1.  每个顶点出现且只出现一次。
2.  若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说。

拓扑排序介绍  
拓扑排序(Topological Order)是指，将一个有向无环图(Directed Acyclic Graph简称DAG)进行排序进而得到一个有序的线性序列。  
这样说，可能理解起来比较抽象。下面通过简单的例子进行说明！   
例如，一个项目包括A、B、C、D四个子部分来完成，并且A依赖于B和D，C依赖于D。现在要制定一个计划，写出A、B、C、D的执行顺序。这时，就可以利用到拓扑排序，它就是用来确定事物发生的顺序的。  
在拓扑排序中，如果存在一条从顶点A到顶点B的路径，那么在排序结果中B出现在A的后面。  
拓扑排序的算法图解  
拓扑排序算法的基本步骤：  
1. 构造一个队列Q(queue) 和 拓扑排序的结果队列T(topological)；   
2. 把所有没有依赖顶点的节点放入Q；   
3. 当Q还有顶点的时候，执行下面步骤：   
3.1 从Q中取出一个顶点n(将n从Q中删掉)，并放入T(将n加入到结果集中)；   
3.2 对n每一个邻接点m(n是起点，m是终点)；   
3.2.1 去掉边<n,m>;   
3.2.2 如果m没有依赖顶点，则把m放入Q;   
注：顶点A没有依赖顶点，是指不存在以A为终点的边。  
![Center][]  
以上图为例，来对拓扑排序进行演示。  
![Center 1][]  
第1步：将B和C加入到排序结果中。   
    顶点B和顶点C都是没有依赖顶点，因此将C和C加入到结果集T中。假设ABCDEFG按顺序存储，因此先访问B，再访问C。访问B之后，去掉边<B,A>和<B,D>，并将A和D加入到队列Q中。同样的，去掉边<C,F>和<C,G>，并将F和G加入到Q中。   
    (01) 将B加入到排序结果中，然后去掉边<B,A>和<B,D>；此时，由于A和D没有依赖顶点，因此并将A和D加入到队列Q中。   
    (02) 将C加入到排序结果中，然后去掉边<C,F>和<C,G>；此时，由于F有依赖顶点D，G有依赖顶点A，因此不对F和G进行处理。   
第2步：将A,D依次加入到排序结果中。   
    第1步访问之后，A,D都是没有依赖顶点的，根据存储顺序，先访问A，然后访问D。访问之后，删除顶点A和顶点D的出边。   
第3步：将E,F,G依次加入到排序结果中。  
因此访问顺序是：B -> C -> A -> D -> E -> F -> G

#include<cstdio>
    #include<cstring>
    #include<queue>
    #include<algorithm>
    #define maxn 100001
    typedef long long ll;
    using namespace std;
    int tupo[maxn];
    struct A
    {
        int next;
        int to;
    }f[maxn];
    int head[maxn];
    int rudu[maxn];
    int cnt;
    void build(int u,int v)
    {
        f[cnt].to=v;
        f[cnt].next=head[u];
        head[u]=cnt++;
    }
    int main()
    {
        int n,m;
        while(~scanf("%d %d",&n,&m))
    	{
    	    queue<int> q;
    	    memset(head,-1,sizeof(head));
            memset(rudu,0,sizeof(rudu));
            int s,e;
            cnt=1;
            for(int i=1;i<=m;i++)
    		{
                scanf("%d %d",&s,&e);
                build(s,e);
                rudu[e]++;
            }
            for(int i=1;i<=n;i++)
            	if(rudu[i]==0)
                    q.push(i);
            int kk=0;
            while(!q.empty())
    		{
                int fr=q.front();
                q.pop();
                tupo[kk++]=fr;
                for(int i=head[fr];i!=-1;i=f[i].next)
    			{
                    int to=f[i].to;
                    rudu[to]--;
                    if(rudu[to]==0)
    					q.push(to);
                }
            }
            for(int i=0;i<n;i++)
    		{
                printf("%d\n",tupo[i]);
            }
        }
        return 0;
    }
    
    /*
    1 2
    4 1
    1 5
    1 9
    10 3
    5 10
    8 9
    6 9
    3 6
    4 5
    */

结果：4 7 8 1 5 2 10 3 6 9

[Center]: /images/20220609/41051de855934362acc2d9529c73df7f.png
[Center 1]: /images/20220609/984e597c431049f0b3f1417ade8e4177.png