拓扑排序详解（梅开二度之dfs版按字典序输出拓扑路径+dfs版输出全部拓扑路径

什么是拓扑排序？

先穿袜子再穿鞋，先当孙子再当爷。这就是拓扑排序！

拓扑排序说白了其实不太算是一种排序算法，但又像是一种排序（我是不是说了个废话qwq）

他其实是一个有向无环图（DAG, Directed Acyclic Graph的所有顶点的线性序列，该序列需要满足两个条件：

每个节点只能出现一次
若存在一条A到B到路径，则在拓扑序列中A必然出现在B前面

而有向无环图才具有拓扑排序，非DAG图则没有拓扑排序一说

先看一道拓扑排序的水题趴(>_<)

UVa 10305 - Ordering Tasks

题意：

有n个任务要做，有m个要求，每个要求有两个数x，y，要求x必须在y之前执行，让你输出一种执行任务的序列

这里窝给出两种方法，一种dfs，一种bfs，两种建图方法，一种邻接链表，一种链式前向星

再看一道稍微有点变化的拓扑排序

1089.拓扑排序

题意：

给定一个有向图，若存在环，输出IMPOSABLE，否则输出一行用一个空格隔开的拓扑排序的结果，若存在多个结果，输出字典序最小的。

既需要判断是否有环也需要输出字典序最小的

同样的，窝给出两种方法，一种dfs，一种bfs，来判环以及输出字典序最小

bfs版拓扑排序

问题1:

主要思想就是找出所有入度为0的点，给他们扔进队列里面，然后对对列的元素进行如下操作：取队首赋为now，扔队首，遍历now的所有后继节点，并让他们的入度减1，同时进行判断入度是否减到了0，如果到0了，就扔进对列，一直循环到对列为空结束

如果需要按字典序输出，就用优先队列

邻接链表建图：

使用vector，注意要每次初始化vector

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 200000 + 50
#define endl '\n'
#define seed 13331
#define mod 1000000000 + 7
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
//不开longlong见祖宗！
//inline __int128 read(){__int128 x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-'){f = -1;}ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
//inline void print(__int128 x){if(x < 0){putchar('-');x = -x;}if(x > 9){print(x / 10);}putchar(x % 10 + '0');}
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
inline void write(int x){if (x < 0) {x = ~x + 1; putchar('-');}if (x > 9){write(x / 10);}putchar(x % 10 + '0');}

int n, m, a, b, now;
vector<vector<int> >tr;
int in[MAX];
queue<int>q;
bool vis[MAX];

void topsort(){
    for(int i = 1; i <= n; ++i){
        if(in[i] == 0)q.push(i);//找到所有入度为0的点，入队
    }
    while (!q.empty()) {
        now = q.front();q.pop();//取队首，记得pop
        if(vis[now])continue;//如果访问过就跳过
        vis[now] = 1;//没访问就标记一下
        cout<<now<<' ';//输出
        for(int i = 0; i < tr[now].size(); ++i){
            int v = tr[now][i];
            --in[v];//入度减一
            if(in[v] == 0)q.push(v);//如果入度为0，入队
        }
    }
    cout<<endl;
}

int main(){
    io;
    while (cin>>n>>m && (n + m)) {
        mem(in, 0);
        mem(vis, 0);
        tr = vector<vector<int> >(n + 1);//初始化
        for(int i = 1; i <= m; ++i){
            cin>>a>>b;
            tr[a].push_back(b);//b为a的后继节点，就无脑塞
            ++in[b];//b的入度加一
        }
        topsort();
    }
    return 0;
}

链式前向星建图：

主要的思想没有变化，只不过用的是链式前向星建图，相当于板子而已，写多了就习惯了，再加上如果怕vector被卡的话就采用链式前向星

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 200000 + 50
#define endl '\n'
#define seed 13331
#define mod 1000000000 + 7
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
//不开longlong见祖宗！
//inline __int128 read(){__int128 x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-'){f = -1;}ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
//inline void print(__int128 x){if(x < 0){putchar('-');x = -x;}if(x > 9){print(x / 10);}putchar(x % 10 + '0');}
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
inline void write(int x){if (x < 0) {x = ~x + 1; putchar('-');}if (x > 9){write(x / 10);}putchar(x % 10 + '0');}

int n, m, a, b, tot, now;
int head[MAX];
int in[MAX];
bool vis[MAX];
struct ran{
    int to, next;
}tr[MAX];
queue<int>q;

void init(){//初始化
    mem(in, 0);
    mem(vis, 0);
    mem(tr, 0);
    mem(head, -1);
    tot = 0;
}

void built(int u, int v){//建图
    tr[++tot].to = v;
    tr[tot].next = head[u];
    head[u] = tot;
}

void topsort(){
    for(int i = 1; i <= n; ++i){
        if(in[i] == 0)q.push(i);
    }
    while (!q.empty()) {
        now = q.front();q.pop();
        if(vis[now])continue;
        vis[now] = 1;
        cout<<now<<' ';
        for(int i = head[now]; i != -1; i = tr[i].next){
            int v = tr[i].to;
            --in[v];
            if(in[v] == 0)q.push(v);
        }
    }
    cout<<endl;
}

int main(){
    io;
    while (cin>>n>>m && (n + m)) {
        init();
        for(int i = 1; i <= m; ++i){
            cin>>a>>b;
            built(a, b);
            ++in[b];
        }
        topsort();
    }
    return 0;
}

问题2:

如何判环呢？

我们只需要记录输出的数字的个数是否等于n即可

如何输出字典序最小呢？

只需要将queue换成priority_queue即可

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 200000 + 50
#define endl '\n'
#define seed 13331
#define mod 1000000000 + 7
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
//不开longlong见祖宗！
//inline __int128 read(){__int128 x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-'){f = -1;}ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
//inline void print(__int128 x){if(x < 0){putchar('-');x = -x;}if(x > 9){print(x / 10);}putchar(x % 10 + '0');}
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
inline void write(int x){if (x < 0) {x = ~x + 1; putchar('-');}if (x > 9){write(x / 10);}putchar(x % 10 + '0');}

int n, m, tot, x, y, now;
struct ran{
    int to, next;
}tr[MAX];
int in[1005];
int head[MAX];
bool vis[MAX];
int ans[1005];
int num;
priority_queue<int, vector<int>, greater<int> >q;//优先队列

void built(int u, int v){
    tr[++tot].to = v;
    tr[tot].next = head[u];
    head[u] = tot;
}

void topu(){
    tot = 0;
    while (!q.empty()) {
        now = q.top();q.pop();
        if(vis[now])continue;
        ++tot;//记录数量
        vis[now] = 1;
        ans[++num] = now;
        for(int i = head[now]; i != -1; i = tr[i].next){
//            cout<<tr[i].to;
            --in[tr[i].to];
            if(in[tr[i].to] == 0)q.push(tr[i].to);
        }
    }
}


int main(){
    io;
    n = IntRead();
    m = IntRead();
    mem(head, -1);
    mem(tr, -1);
    for(int i = 1; i <= m; ++i){
        x = IntRead();
        y = IntRead();
        built(x, y);
        ++in[y];
    }
    for(int i = 1; i <= n; ++i){
        if(in[i] == 0){
            q.push(i);
        }
    }
    topu();
    if(tot == n){//如果输出的数的数量等与n，就说明没有环
        for(int i = 1; i <= n; ++i){
            i == 1 ? cout<<ans[i] : cout<<' '<<ans[i];
        }
        cout<<endl;
    }
    else cout<<"IMPOSABLE\n";
    return 0;
}

dfs版拓扑排序

问题1:

之前写拓扑排序都是用的bfs的方法，没寻思dfs还可以写，直到我做了一下oj的1089，判环的时候发现可以用dfs判环，然后我就好奇如何用dfs进行拓扑排序、如何按字典序输出拓扑序列、如何将所有的拓扑序列都输出，发现网上很少有教这些的，就寻思自己写一写，于是就有了这篇博客o(≧v≦)o

刚开始觉得用dfs写拓扑排序很复杂，这他么的dfs能怎么排？

要从入度为0出发么？

如果有多个入度为0的点，每个都dfs一遍么，那他们会不会乱套？

后来学会了以后感觉简直不可思议，真的是奈何自己没文化，一句wc行天下

首先我们讨论一下拓扑排序的性质，对于一个图，他可能会有好多种拓扑排序，但他们满足一个规律：那就是如果存在有向边

u->v

, 那么结点

必须排在

之前（前驱）。同时这种性质具有传递性，也就是说如果同时存在

v->t,

那么满足

在

之前。同样的，如果

和

两个结点在图中并不满足这种性质，那么谁在前谁在后就无所谓了。正是利用这个规则，我们进行dfs的顺序是无所谓的。

为何？因为我们从

root

结点开始dfs一遍，可以找到所有的必须在这个

root

结点之后的点，那么我们就满足了拓扑序的规则了，那么我们无论先dfs(u)还是先dfs(v), 都不会违背这个规则（除非有环），那么同时我们只要按照某种合理的方式存储所有这些点，那么他们就是拓扑序了。

什么是合理的方式？栈！考量一个dfs(u), 在它结束该退出时，它代表它的结点u。在dfs递归中，什么点会最先exit？没有后继结点的点（或者后继已入栈的点）！那么把所有点分成两个集合，一个是待处理的点集D，一个是已拓扑排序后的点集A，当且仅当D中某个点没有后继结点（或该后继结点已经加入了点集A中）时，它可以从D转移到A，而dfs的回溯方式，恰恰就自动实现了这样的功能。结合代码更容易体会。

不需要判环，输出一种拓扑排序（链式前向星法

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 200000 + 50
#define endl '\n'
#define seed 13331
#define mod 1000000000 + 7
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
//不开longlong见祖宗！
//inline __int128 read(){__int128 x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-'){f = -1;}ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
//inline void print(__int128 x){if(x < 0){putchar('-');x = -x;}if(x > 9){print(x / 10);}putchar(x % 10 + '0');}
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
inline void write(int x){if (x < 0) {x = ~x + 1; putchar('-');}if (x > 9){write(x / 10);}putchar(x % 10 + '0');}

int n, m, a, b, tot, now;
int head[MAX];
int in[MAX];
bool vis[MAX];
struct ran{
    int to, next;
}tr[MAX];
stack<int>s;

void init(){
    mem(in, 0);
    mem(vis, 0);
    mem(tr, 0);
    mem(head, -1);
    tot = 0;
}

void built(int u, int v){
    tr[++tot].to = v;
    tr[tot].next = head[u];
    head[u] = tot;
}

void dfs(int u){
    vis[u] = 1;//标记一下这个点来过
    for(int i = head[u]; i != -1; i = tr[i].next){
        int v = tr[i].to;
        if(!vis[v])dfs(v);//下一个点如果没来过，就dfs下一个点
    }
    s.push(u);//搜完了就入栈
}

int main(){
    io;
    while (cin>>n>>m && (n + m)) {
        init();
        for(int i = 1; i <= m; ++i){
            cin>>a>>b;
            built(a, b);
            ++in[b];
        }
        for(int i = 1; i <= n; ++i){
            if(!vis[i])dfs(i);
        }
        while (!s.empty()) {
            cout<<s.top()<<' ';s.pop();
        }
        cout<<endl;
    }
    return 0;
}

问题2:

如何判环？

判环只是在dfs的基础上稍作修改，其最主要的是对vis数组的含义有所扩展，以及对下一个节点进行dfs判断

不判环对vis只代表该点也没有被访问，而现在vis有三个值，-1，0，1. -1代表已经访问过，但不是当前dfs访问的， 1表示访问过，且是当前的dfs访问的，意味着有环（

u->v,v->t,t->u

），0表示没访问过

dfs返回的是以root为根节点的后续有没有环，所以我们需要对每个点都去跑一遍dfs，当然，如果已经访问过了，就没必要去dfs他了

伪代码

//判断是否有环(true 没有; false 有)
bool dfs(u) {
	本趟节点标记;
	for(遍历以u为入弧的定点){
			if(是本趟节点）return false;
			else if(如果没访问过) {
				if(子节点有环)return false;
			}
		}
		//表示这个节点的到底都没有环
		倒着将沿途的节点加入拓扑队列    //因为这是递归的返回,就是到头回来的过程
		return true;
	}
bool topoSort(){
	for(遍历节点){
		if(没访问过）{
			if(有环) return false;
		}
	}
	//所有节点都没环
	return true;
}

两句if 可以合成为 
if(没访问过 && 有环)return false;

核心代码如下：

bool dfs(int u)
{
    vis[u] = 1;
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if (vis[v] == 1) return false;
        if (vis[v] == 0 && !dfs(v)) return false;
    }
    vis[u] = -1;
    s.push(u);
    return true;
}

bool topsort(){
    mem(vis, 0);
    for(int i = n; i >= 1; --i){
        if(!vis[i]){
            if(!dfs(i))return false;
        }
    }
    return true;
}

如何按照字典序输出呢？

我们输出的时候是通过栈输出的，栈是先进后出，所以要想字典序最小，只需要让大的先进去，小的后进去，所以我们采用邻接链表的方法存图，存完图以后对每一个root节点的后续节点从大到小进行排序，这样dfs的时候，顺着取后继节点的时候就是从大到小。然后我们for循环的时候，也是从n开始到1去循环即可

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 200000 + 50
#define endl '\n'
#define seed 13331
#define mod 1000000000 + 7
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
//不开longlong见祖宗！
//inline __int128 read(){__int128 x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-'){f = -1;}ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
//inline void print(__int128 x){if(x < 0){putchar('-');x = -x;}if(x > 9){print(x / 10);}putchar(x % 10 + '0');}
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
inline void write(int x){if (x < 0) {x = ~x + 1; putchar('-');}if (x > 9){write(x / 10);}putchar(x % 10 + '0');}

int n, m, a, b, cnt;
vector<vector<int> >ma;
int vis[MAX];
stack<int>s;

bool cmp(int x, int y){
    return x > y;
}


bool dfs(int u){
    vis[u] = -1;
    for(int i = 0; i < ma[u].size(); ++i){
        if(vis[ma[u][i]] == -1)return false;
        else if(vis[ma[u][i]] == 0){
            dfs(ma[u][i]);
        }
    }
    vis[u] = 1;
    s.push(u);
    return true;
}

bool topsort(){
    mem(vis, 0);
    for(int i = n; i >= 1; --i){//从大的开始
        if(!vis[i]){
            if(!dfs(i))return false;
        }
    }
    return true;
}


int main(){
    n = IntRead();
    m = IntRead();
    ma = vector<vector<int> >(n + 1);//初始化
    for(int i = 1; i <= m; ++i){
        a = IntRead();
        b = IntRead();
        ma[a].push_back(b);
    }
    for(int i = 1; i <= n; ++i){//排序！
        sort(ma[i].begin(), ma[i].end(), cmp);
    }
    bool p = topsort();
    if(p == false)cout<<"IMPOSABLE\n";
    else {
        while (s.size() != 1) {
                cout<<s.top()<<" ";
                s.pop();
            }
            cout<<s.top()<<endl;
    }
    return 0;
}

输出所有的拓扑序列

就是一个dfs，每次dfs都让入度为0且没有标记的点 i 去更新其后继节点，然后将 i 放进ans数组中，然后标记一下，去dfs(num + 1)，回溯的时候，就把所有更新的点的入度都加回来，把 i 重新标记为0。

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 200000 + 50
#define endl '\n'
#define seed 13331
#define mod 1000000000 + 7
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
//不开longlong见祖宗！
//inline __int128 read(){__int128 x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-'){f = -1;}ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
//inline void print(__int128 x){if(x < 0){putchar('-');x = -x;}if(x > 9){print(x / 10);}putchar(x % 10 + '0');}
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
inline void write(int x){if (x < 0) {x = ~x + 1; putchar('-');}if (x > 9){write(x / 10);}putchar(x % 10 + '0');}

int n, m, a, b, tot, now;
int head[MAX];
int in[MAX];
bool vis[MAX];
struct ran{
    int to, next;
}tr[MAX];
int ans[MAX];

void init(){
    mem(in, 0);
    mem(vis, 0);
    mem(tr, 0);
    mem(head, -1);
    tot = 0;
}

void built(int u, int v){
    tr[++tot].to = v;
    tr[tot].next = head[u];
    head[u] = tot;
}

void dfs(int num){
    if(num == n + 1){//如果数量到n+1，就输出
        for(int i = 1; i <= n; ++i){
            cout<<ans[i]<<' ';
        }
        cout<<endl;
    }
    for(int i = 1; i <= n; ++i){
        if(!in[i] && !vis[i]){//入度为0，且没被标记过
            int u = i;
            for(int j = head[u]; j != -1; j = tr[j].next){
                --in[tr[j].to];//遍历所有后继节点
            }
            vis[u] = 1;//标记一下点i
            ans[num] = u;//把他放进ans数组
            dfs(num + 1);//继续搜
            for(int k = head[u]; k != -1; k = tr[k].next){
                ++in[tr[k].to];
            }//把入度更新回来
            vis[u] = 0;//取消标记
        }
    }
    return;
}

int main(){
    io;
    while (cin>>n>>m && (n + m)) {
        init();
        for(int i = 1; i <= m; ++i){
            cin>>a>>b;
            built(a, b);
            ++in[b];
        }
        dfs(1);
    }
    return 0;
}

拓扑排序详解（梅开二度之dfs版按字典序输出拓扑路径+dfs版输出全部拓扑路径

什么是拓扑排序？

先穿袜子再穿鞋，先当孙子再当爷。这就是拓扑排序！

UVa 10305 - Ordering Tasks

题意：

1089.拓扑排序

题意：

bfs版拓扑排序

问题1:

邻接链表建图：

链式前向星建图：

问题2:

dfs版拓扑排序

问题1:

问题2:

输出所有的拓扑序列

继续阅读

Codeforces 1417 D. Make Them Equal(思维+构造)

查找算法之二分查找查找算法之二分查找

查找算法学习之二分查找（Python版本）——BinarySearch

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

Command Network(POJ 3164)---定根最小树形图模板题题目描述输入格式输出格式输入样例输出样例分析源程序

开源低带宽语音编解码器

241 Different Ways to Add Parentheses（C代码版）

【趋高机器视觉】机器视觉技术原理解析及解决方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制规程及特点4． CSMA/CD协议5． CSMA/CD的优点6．结束语

极大似然法(ML)与最大期望法(EM)

C++ 第十五周报告1--《冒泡法排序》

笔试面试题目：滑动窗口(二)

数据结构与算法（27）——排序（二）

Dijkstra--简易版（最短路径）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

hdu7108哈希