DAG拓扑排序

我就是我 2024-04-17 05:59 66阅读 0赞

一个庞大的、复杂的系统工程，往往有一些步骤需要先完成某些工作才能进行，于是要想高效地完成整个工程，就要搞清楚先完成哪些工作，再完成哪些工作，也就是完成的先后顺序。举个简单的例子，计算机专业的学生需要完成整个学业需要学习很多课程，而这些课程之间是相互关联的，不学会一门编程语言（比如C++）就不能学习数据结构，这样编程语言就叫做数据结构的先导课程，需要先学习编程语言再学习数据结构。DAG拓扑排序算法应运而生。

上DAG拓扑排序算法代码：

#include <cstdio>
    #include <cstring>
    #include <vector>
    using namespace std;
    bool mp[501][501];
    int indegree[501];
    vector<int> ans;
    int n,m;
    int main()
    {
        //输入顶点数和边数
        while(~scanf("%d%d",&n,&m))
        {
            ans.clear();
            int i,j;
            memset(mp,0,sizeof(mp));
            memset(indegree,0,sizeof(indegree));
            for(i=0;i<m;i++)
            {
                int a,b;
                scanf("%d%d",&a,&b);
                //注意有重边的情况
                if(mp[a][b]==false)
                {
                    mp[a][b]=true;
                    indegree[b]++;
                }
            }
            while(true)
            {
                bool flag=true;
                for(i=1;i<=n;i++)
                {
                    if(indegree[i]==0)
                    {
                        flag=false;
                        ans.push_back(i);
                        indegree[i]--;
                        for(j=1;j<=n;j++)
                        {
                            if(mp[i][j]==true)
                            {
                                indegree[j]--;
                            }
                        }
                        break;
                    }
                }
                if(flag)
                    break;
            }
            int len=ans.size();
            for(i=0;i<len;i++)
            {
                if(i>0)
                    printf(" ");
                printf("%d",ans[i]);
            }
            printf("\n");
        }
        return 0;
    }

初始化图时统计各个顶点的入度。

**每次都找入度为0的顶点加入最终结果ans：找到入度为0的顶点，就让自己的入度再减1变为-1，这样下一次找入度为0的顶点时就不会再找到这个顶点了；与此同时，将所有与该顶点相连的顶点的入度都减1，意味着当前顶点已经被删除。**

直到找不到入度为0的顶点为止，即全部顶点都已被删除。

此时数组ans中的元素从前往后走就是拓扑排序的结果。

**欢迎大家关注/订阅我的微信公众号Code Art Online，我会在我的公众号分享个人见闻，发现生活趣味；这里不仅有0和1，还有是诗和远方↓↓↓**

![20200227123106884.jpg][]

[20200227123106884.jpg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/15/447fae0cbe1e4046af58e4e4dbe21d1f.jpg