拓扑排序详解（梅开二度之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 , 那么结点 u必须排在v之前（前驱）。同时这种性质具有传递性，也就是说如果同时存在v->t, 那么满足u在t之前。同样的，如果u和v两个结点在图中并不满足这种性质，那么谁在前谁在后就无所谓了。正是利用这个规则，我们进行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;
}
