数据结构实验之图论十：判断给定图是否存在合法拓扑序列

痛定思痛。 2022-05-17 12:59 115阅读 0赞

### 有向无环图 ###

一个无环的有向图称作有向无环图(directed acycline graph)，简称DAG图。假设以有向图表示一个工程的施工图或程序的数据流图，则图中不允许出现[回路][Link 1]，如果出现回路，说明了某项活动以它自己为先决条件，显然是荒谬的，工程将无法进行。 \[1\]

### 拓扑排序 ###

拓扑排序是一种对非线性结构的有向图进行线性化的重要手段。在给定的有向图G中，若顶点序列Vi1，Vi2，Vi3，....,Vin，。满足下列条件：若在有向图G中从顶点Vi，到顶点Vj有一条路径，则在序列中顶点Vi必在顶点Vj之前，便称这个序列为一个拓扑序列。求一个有向图拓扑序列的过程称为拓扑排序。  
　　拓扑排序的方法如下：  
　　(1)从图中选择一个人度为O的顶点并输出；  
　　(2)从图中删掉该顶点及其所有以该顶点为弧尾的弧。  
　　反复执行这两个步骤，直到所有的顶点都被输出，输出的序列就是这个无环有向图的拓扑序列。

如果在带权有向图中，用顶点表示事件，用有向边表示活动，边上的权值表示活动的开销，则此带权有向图称为边活动网(activity on edge network)，简称AOE网。AOE网是一个有向无环图。AOE网是用来描述由许多交叉活动组成的复杂计划和工程的方法，比如某工程的AOE网。

在工程中用边表示活动，边上的权表示完成这项活动所需要的时间，顶点表示某项活动的开始，顶点1称为源点（或起点），表示整个工程开始，顶点2称为汇点（或终点），表示整个工程的结束。用AOE网来估算工程的最短工期（完成整个工程至少需要多少时间）以及哪些活动是影响工程进展的关键。

#include<bits/stdc++.h>
    using namespace std;
    int a[20];
    int Map[20][20];
    int n,m,sum;
    void judge()
    {
        queue<int>q;
        for(int i=1;i<=n;i++)
        {
            if(a[i]==0)
                q.push(i);
        }
        while(!q.empty())
        {
            int temp=q.front();
            q.pop();
            sum++;///用来记录是否所有的节点都被输出；
            for(int j=1;j<=n;j++)///用来处理是该节点出度的节点；
            {
                if(Map[temp][j]==1)
                {
                    a[j]--;
                if(a[j]==0)
                    q.push(j);
                }
            }
        }
        if(sum==n)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    int main()
    {
        int u,v;
        while(cin>>n>>m)
        {
            sum=0;
            memset(a,0,sizeof(a));
            memset(Map,0,sizeof(Map));
            for(int i=0;i<m;i++)
            {
                cin>>u>>v;
                Map[u][v]=1;
                a[v]++;///记录当前节点是否有入度；
            }
            judge();
        }
    }

[Link 1]: https://baike.baidu.com/item/%E5%9B%9E%E8%B7%AF/35792