【图论算法】拓扑排序

· · 个人记录

GMQ出品，拓扑排序的概念、堆优化、基础例题及代码详解

一、什么是拓扑排序

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

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

例如，下面这个图：

对于本图而言:它是一个DAG图，那么如何写出它的拓扑排序呢？

一种比较常用的方法：

  1. 从DAG图中选择一个没有前驱（即入度为0）的顶点并输出。

  2. 从图中删除该顶点和所有以它为起点的有向边。

  3. 重复1和2直到当前的DAG图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。

经过如下操作后：

得到拓扑排序后的结果是{1,2, 4, 3, 5}。 通常，一个有向无环图可以有一个或多个拓扑排序序列。

再来一个例子：

二、例题

模板题：1462 -- 【拓扑排序】拓扑排序

[问题描述]
给你一个图，要求你求出拓扑序列。

[输入格式]
第1行为2个空格分开的整数n(2<=n<=200)和m(10<=m<=20000)，分别表示图的顶点数和边数。
第2...m+1行，每行2个空格分开的整数i, j, i表示一条边的起点，j表示终点。

[输出格式]
拓扑序，顶点从1开始编号，若有多个拓扑序，则顶点编号小的优先输出。
若有环，则输出"no solution"。

[样例输入]
22
12
21

[样例输出]
no solution

代码如下（按照最小字典序输出）复杂度为O(N^2^)：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m;
int rd[410],ans[410];
bool mapp[410][410];
int tp() {
    for(int i=1; i<=n; i++) {
        int k;
        for(k=1; k<=n+1; k++) {//寻找入度为0的点
            if(rd[k]==0) {
                break;
            }
        }
        if(k>n) return 0;//环!
        ans[++ans[0]]=k;//按照最小字典序记录拓扑序列
        rd[k]=-1;//标记入度为-1（注：千万不能标记为0）
        for(int j=1; j<=n; j++) {
            if(mapp[k][j]==1) rd[j]--;//删除连边
        }
    }
    return 1;
}
int main() {
    cin>>n>>m;
    for(int i=1; i<=m; i++) {
        int x,y;
        cin>>x>>y;
        rd[y]++;//统计入度
        mapp[x][y]=1;//邻接矩阵存储
    }
    if(tp()) {//无环
        for(int i=1; i<=ans[0]; i++) {
            cout<<ans[i]<<" ";
        }
        return 0;
    }
    cout<<"no solution"<<endl;//有环
    return 0;
}

变形题：1464 -- 【拓扑排序】被遗忘的时光

[问题描述]
Lost-Monkey赢了精灵，精灵告诉Lost-Monkey，神庙里被恶魔封印了一个名为Lostangle的天使，如果想把它释放出来，需要将 n 个时间点排序，而精灵只知道 m 条形如 a 在 b 前的信息。
Lost-Monkey一听到有天使，很想见见天使到底长什么样，可惜时间点太多，他觉得这几乎是不可能的任务，好在身为在他旁边的XXX，你，传说中的impossible is nothing，一定知道如何解决啦！！

[输入格式]
第一行n，m；
接下来m行，每行2个数a，b；意义均同上。

[输出格式]
输出文件仅一行，若可以将n个时间点排序，则输出字典序最小的一种方案，否则输出“NO SOLUTION”。

[样例输入]
3 2
1 2
2 3

[样例输出]
1 2 3

[数据范围]
40%的数据,n<=1000，m<=1000
100%的数据,n<=100000，m<=500000

这道题结点数n<=100000

若为了保证字典序最小，按照上一道题的邻接矩阵实现方法时间复杂度为O(N^2^)，必然TLE

可以改进入度为0的点的汇总方式，不跑循环，而是在断边时判断并存储

但如果只用数组存储，虽然复杂度降到了O(n+e)，但是不能按照字典序

这是因为取出入度为0的点时是直接取数组头（否则也得不到优化复杂度的目的），而数组头不一定字典序最小

而什么容器可以维护字典序呢？

我听见你在说：“set！ 优先队列！！！”

这是因为：

较之于队列，优先队列的不同在于它每一次取值取的是队列中的最大（小）值

那么，我们可以用小根堆维护一个优先队列（STL万岁！）

这样可以在O(1)的复杂度内找到字典序最小的入度为0的点

代码如下（按照最小字典序输出）复杂度为O(n+e)：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define maxn 500010
using namespace std;
priority_queue<int,vector<int>,greater<int> >hp;//STL小根堆
int n,m;
int rd[maxn],ans[maxn];
struct star{
    int next,to;
}a[maxn];
int h[maxn],top;
void add(int x,int y) {
    a[++top].to=y;
    a[top].next=h[x];
    h[x]=top;
    return;
}
int tp() {
    for(int i=1; i<=n; i++) {
        if(rd[i]==0) hp.push(i);//入堆
    }
    while(!hp.empty()) {//堆非空
        int x=hp.top();
        hp.pop();//取出堆顶
        ans[++ans[0]]=x;
        for(int i=h[x]; i; i=a[i].next) {
            int y=a[i].to;
            rd[y]--;
            if(rd[y]==0) hp.push(y);//入度为0的点入堆
        }
    }
    if(ans[0]!=n) return 0;//有入度为0的点未取出，即有环
    return 1;
}
int main() {
    cin>>n>>m;
    for(int i=1; i<=m; i++) {
        int x,y;
        cin>>x>>y;
        add(x,y);//前向星存储
        rd[y]++;//统计入度
    }
    if(tp()) {//无环
        for(int i=1; i<=ans[0]; i++) {
            cout<<ans[i]<<" ";
        }
        return 0;
    }
    cout<<"NO SOLUTION"<<endl;//有环
    return 0;
}

变形题：1465 -- 【拓扑排序】奖金

[问题描述]
由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出，Yali Company总经理Mr.Z心情好，决定给每位员工发奖金。公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。
于是Mr.Z下令召开m方会谈。每位参加会谈的代表提出了自己的意见：“我认为员工a的奖金应该比b高！”Mr.Z决定要找出一种奖金方案，满足各位代表的意见，且同时使得总奖金数最少。每位员工奖金最少为100元。
　　
[文件输入]
第一行两个整数n,m，表示员工总数和代表数；
以下m行，每行2个整数a,b，表示某个代表认为第a号员工奖金应该比第b号员工高。

[文件输出]
若无法找到合理方案，则输出“Poor Xed”；否则输出一个数表示最少总奖金。

[样例输入]
2 1
1 2

[样例输出]
201

[数据规模]
80％的数据满足n<=1000，m<=2000；
100％的数据满足n<=10000，m<=20000。

首先构图，若存在条件"a的钱比b多"则从b引-条有向指向a；然后拓扑排序，若无法完成排序则表示问题无解(存在圈)；若可以得到完整的拓扑序列，则按序列顺序进行递推：

设 f[i] 表示第i个人能拿的最少奖金数；

首先所有f[i] =100(题目中给定的最小值)；

然后按照拓扑顺序考察每个点i，若存在有向边(j,i),则表示们必须比f[j]大，因此我们令f[i] = Max { f[i]，f[j]+1 }即可；

递推完成之后所有f[i]的值也就确定了，而答案就等于f[1]+... +f[n]。

代码如下（按照最小字典序输出）复杂度为O(n*e)：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define maxn 500010
using namespace std;
priority_queue<int,vector<int>,greater<int> >hp;//STL小根堆
int n,m;
int rd[maxn],ans[maxn];
struct star{
    int next,to;
}a[maxn];
int h[maxn],top;
void add(int x,int y) {
    a[++top].to=y;
    a[top].next=h[x];
    h[x]=top;
    return;
}
int tp() {
    for(int i=1; i<=n; i++) {
        if(rd[i]==0) hp.push(i);//入堆
    }
    int topp=0;
    while(!hp.empty()) {//堆非空
        int x=hp.top();
        hp.pop();//取出堆顶
        topp++;
        for(int i=h[x]; i; i=a[i].next) {
            int y=a[i].to;
            rd[y]--;
            ans[y]=max(ans[y],ans[x]+1);
            if(rd[y]==0) {
                hp.push(y);//入度为0的点入堆
            }
        }
    }
    if(topp!=n) return 0;//有入度为0的点未取出，即有环
    return 1;
}
int main() {
    cin>>n>>m;
    for(int i=1; i<=n; i++) {
        ans[i]=100;
    }
    for(int i=1; i<=m; i++) {
        int x,y;
        cin>>x>>y;
        add(y,x);//前向星存储
        rd[x]++;//统计入度
    }
    if(tp()) {//无环
        int sum=0;
        for(int i=1; i<=n; i++) {
            sum+=ans[i];
        }
        cout<<sum;
        return 0;
    }
    cout<<"Poor Xed"<<endl;//有环
    return 0;
}

拓扑排序概念内容引自简书 图片来源：简书、百度百科 题目来源：Did及Xinyue 代码：GMQ原创出品 代码与堆优化详解：GMQ原创出品 有转载需求请私信：[email protected]