快速入手拓扑排序

Hexarhy · 2019-01-26 23:41:36 · 个人记录

最近一次更新：2021.8.23

1.前言

在正式讲拓扑排序之前，我们来引入一下，以便各位更好理解。

首先，你想学习计算机的原理怎么办？肯定有很多前置知识啊！流程图比如像下面：

很明显，此时你需要按一定顺序学习才能彻底了解计算机原理。我们把这个顺序叫做拓扑序列。此时用拓扑排序即可求出。

前置知识：图的建立与遍历。

2.基本思路 & 实现

首先，对于点的关系，大致分为两种种关系：

先后关系，如上图的 “数学” 与 “物理学” 的关系。
并列关系（通俗讲就是 “没有关系”），如上图的 “物理学” 和 “计算机发展史” 的关系。

不难发现，因为有了并列关系，拓扑序列不一定是唯一的。

如上图，可以得到很多个拓扑序列，这里只举一个例子。

上图的一个拓扑序列：12345678

不难发现，拓扑排序的时候，大家总会找入度为 0 的点，因为这是你不用学习的点，可以直接解锁。

找到了之后，就可以把这个点放到序列里。那么随之就有新的点的入度为 0。然后重复上述步骤直到全部点都遍历完。

以上就是拓扑排序的基本思路。我们可以简述为：

从图中，选择一个入度为 0 的点，并输出该点；
从图中，删除该顶点，以及相关联的边；
重复上述步骤，直到遍历完所有点。

下面模拟一遍拓扑排序的过程（可跳过）。

3. 模拟思路

入度为 0 的点有 1 和 5。我们将其加入拓扑序列并删除边 A,B,H。
入度为 0 的点有 2 和 4。我们将其加入拓扑序列并删除边 C,D,G。
入度为 0 的点有 3。我们将其加入拓扑序列并删除边 E,F。
入度为 0 的点有 6 和 7。我们将其加入拓扑序列并删除边 I,J。
入度为 0 的点有 8。拓扑排序结束。

最终拓扑序列为：15243678。

4. 代码实现

拓扑排序算法实现也很直接。

设置一个队列,将所有入度为 0 的顶点入队。找入度为 0 的点,只要依次出队即可。删除边的操作转化为将该点关联的所有点的入度减 1。下文代码采用这个思路。

很明显，由于要改变点的入度，因此我们需要一个数组保存入度（核心），并执行相应操作。

对于有向无环图，输出拓扑序列的程序。程序如下：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;

const int MAXN=10005;
int n,m,cnt;//cnt是为了存储ans数组的下标
bool a[MAXN][MAXN];//邻接矩阵建图用
int indeg[MAXN],ans[MAXN];
//indeg[i]是第i个点的入度；ans[]是答案队列
queue <int> q;//

void input(void)
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        a[x][y]=1;
        indeg[y]++;//建图，同时统计入度
    }
} 

void topo_sort(void)
{
    for(int i=1;i<=n;i++)
     if(indeg[i]==0)
      q.push(i);//将所有入度为0的点入队
    while(!q.empty())//开始搜索
    {
        const int u=q.front();
        ans[++cnt]=u;//入度为0的点记得放到答案队列里
        q.pop();
        for(int i=1;i<=n;i++)
         if(a[u][i])//删边的操作转化为入度减1
         {
            indeg[i]--;
            if(indeg[i]==0)//如果这个点变成入度为0，入队列
             q.push(i); 
         }
    }
}

void output(void)
{
    for(int i=1;i<=n;i++)
     cout<<ans[i]<<' ';
}

int main()
{
    input();
    topo_sort();
    output();
    return 0;
}

此程序时间复杂度显而易见，邻接矩阵时间复杂度 O(n^2)。但是用邻接链表的话，由于数据结构不同，时间复杂度O(n+e)。

一般来说，链表会好些，不过某些时候矩阵更方便表示。

看到这，是否会有人好奇，为什么不需要的 vis 数组来标记是否走过这点呢？

答案是不用标记。因为在某个点被弹出队列时，队列中的点一定不是它的前驱，那个点就一定不会再次入队。

因此，既然节点不会二次入队，所以就不需要 vis 数组啦！同时，也因为拓扑排序保证每个节点、每条边只被访问过一次，因此时间复杂度是线性的，为O(n+e)（前提是你用的邻接链表）。

继续观察下图：

你可以很明显的发现，拓扑排序的对象只能是个有向无环图（简称DAG）！如果有闭环，那么你将没有入度为 0 的点产生，拓扑排序就异常终止。

所以，判断这个图是否有闭环就显得很重要！该如何判断呢？（会的可以跳过）

这里就只介绍一种简单的方法：用拓扑排序本身。

前面说到拓扑排序保证每个节点、每条边只被访问过一次，因此我们只要看一下答案数组存储个数有没有节点数那么多，就可以判断是否有环。有环的话，那么节点就无法入队，答案就会少。程序如下（代码就多了一个 if 而已）：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;

const int MAXN=10005;
int n,m,cnt;
bool a[MAXN][MAXN];
int indeg[MAXN],ans[MAXN];
queue <int> q;

void input(void)
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        a[x][y]=1;
        indeg[y]++;
    }
} 

void topo_sort(void)
{
    for(int i=1;i<=n;i++)
     if(indeg[i]==0)
      q.push(i);
    while(!q.empty())
    {
        const int u=q.front();
        ans[++cnt]=u;//判断环的核心，看答案数组是否有n个
        q.pop();
        for(int i=1;i<=n;i++)
         if(a[u][i])
         {
            indeg[i]--;
            if(indeg[i]==0)
             q.push(i); 
         }
    }
}

void output(void)
{
    if(cnt<n)//判断是否有环，答案队列不足即有环
    {
        cout<<"No solution!"<<endl;
        return;
    }
    for(int i=1;i<=n;i++)
     cout<<ans[i]<<' ';
}

int main()
{
    input();
    topo_sort();
    output();
    return 0;
}

5. 例题

值得一提的是，拓扑排序通常都是配合其他算法综合考察，很多时候是个辅助切图论题的好帮手。下面给出几道例题。

P4017 最大食物链计数：一道比较简单的题目，适合新手练。
P1038 神经网络：拓扑排序比较经典题目。
P1983 车站分级：NOIp 压轴题，拓扑排序+递推，建图是一大难点，值得一刷。
P1137 旅行计划：拓扑排序+DP。可以进 blog 里看题解。
P3243 [HNOI2015]菜肴制作：正解一点就通。

题解 P1137 旅行计划

这道题目大家一看就能发现，只能往东边走，并且有个入度为 0 的起点，因此这是一个有向无环图，可以进行拓扑排序。

那么我们要拓扑序列怎么做呢？由于拓扑序列中，前面的点总是后面的点的前驱，因此可以进行 dp。

而 dp 式子也很明显，这个城市的路线只能由前面的城市过来（这也像拓扑），因此跟自己与前面城市路线 +1, \max 一下，答案就出来。

具体看注释，参考程序如下：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;

const int MAXN=100005;
int n,m,cnt;
int indeg[MAXN],f[MAXN],a[MAXN];
//三个数组分别表示：入度、dp数组、拓扑序列
struct node
{
    int to,next;
}edge[MAXN<<2];
int head[MAXN],sum;

void add(const int& x,const int& y)
{
    edge[++sum].next=head[x];
    edge[sum].to=y;
    head[x]=sum;
}

void input(void)
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        indeg[y]++;//统计入度
    }
}

void topo_sort(void)//按上面教程说得来就行了
{
    queue <int> q;
    for(int i=1;i<=n;i++)
     if(!indeg[i])//初始化队列
      q.push(i);
    while(!q.empty())
    {
        const int tmp=q.front();
        q.pop();
        a[++cnt]=tmp;//把队列里的入度为0的点存进拓扑序列
        for(int i=head[tmp];i!=0;i=edge[i].next)//遍历一遍图
        {
            const int now=edge[i].to;
            indeg[now]--;
            if(!indeg[now])
             q.push(now);
        }
    }
}

void dp(void)
{
    for(int i=1;i<=n;i++)
     f[i]=1;//每个城市到本身都至少有1条路线
    for(int i=1;i<=n;i++)//每个城市都遍历一遍
    {
        const int tmp=a[i];//注意遍历的是拓扑序列里的城市，此时保证tmp是now的前驱
        for(int j=head[tmp];j!=0;j=edge[j].next)//遍历图
        {
            const int now=edge[j].to;
            f[now]=max(f[now],f[tmp]+1);//把有关联的城市都max一下
        }
    }   
}

void output(void)
{
    for(int i=1;i<=n;i++)
     printf("%d\n",f[i]);
}

int main()
{
    input();
    topo_sort();
    dp();
    output();
    return 0;
}

6. 参考与鸣谢

感谢@zthgreat的一篇博客；
感谢@非我非非我的一篇博客；
感谢@Tartarusi的一篇博客；
感谢@Ufowoqqqo以前的指导；