拓扑排序 用dfs或者bfs

拓扑排序是找DAG（有向无环图）

拓扑排序从数据结构原理上说是不断找对应入度为0的点，找到就删去这个点和从此点出的边。这对应的其实是用bfs的方法，所以用bfs得到的其实除了判断还有每次找的出度为0的点（顺序不唯一），而dfs得到的是这个环的路径。(反正我一般都是并查集判断的。。)

先说bfs：

void bfs_topsort(){
	queue<int > q;
	int sum=0;
	for(int i=1;i<=n;i++)
		if(in[i]==0) //in[]数组保存的是每个点的入度，找到入度为0的点
		q.push(i),sum++;

	int cnt=0;
	while(!q.empty()){
		int now=q.front();q.pop();
		tp[cnt++]=now;ss.push(now);//应该直接顺序保存，把这个ss看成queue,我懒
		for(int i=head[now];~i;i=e[i].next){
			in[e[i].to]--; //删边
			if(in[e[i].to]==0){
				q.push(e[i].to);
				sum++;
			}
		}
	}
	if(sum<n){
		cout<<"有环:"<<endl;
		print(); //打每次度数为0的点
	}else cout<<"无环"<<endl; 
}

dfs是对应遍历边，如果从当前点遍历到的点之前遍历过了，就有环:

int t,c[maxn];
bool dfs(int x){
	c[x]=-1;//正在遍历中
	for(int i=head[x];~i;i=e[i].next){
		if(c[e[i].to]==-1) return false;//存在环;
		else if(!c[e[i].to] && !dfs(e[i].to)) 
                {ss.push(e[i].to);return false;}//dfs是逆序的，栈保存
	}
	c[x]=1;//遍历结束 
	return true;
}
void dfs_topsort(){
	t=n;
	for(int i=1;i<=n;i++)
	if(!c[i] && !dfs(i)){
		cout<<"有环："<<endl;print();
		return; 
	}
	cout<<"无环"; 
}

下面贴测试代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 500;
struct EG{
	int to,next,from;
}e[maxn];
int n,m,cnt;
int head[maxn],in[maxn],tp[maxn];
stack<int> ss;
void add(int a,int b){
	e[++cnt].to = b;
	e[cnt].from=a;
	e[cnt].next = head[a];
	head[a] = cnt;
}
void init(){
	memset(head,-1,sizeof head);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int a,b;scanf("%d %d",&a,&b);
		add(a,b);
		in[b]++;
	}
}
void print(){
			while(!ss.empty()){
			cout<<ss.top()<<" ";
			ss.pop();
		}
		cout<<endl;
}
void bfs_topsort(){
	queue<int > q;
	int sum=0;
	for(int i=1;i<=n;i++)
		if(in[i]==0)
		q.push(i),sum++;

	int cnt=0;
	while(!q.empty()){
		int now=q.front();q.pop();
		tp[cnt++]=now;ss.push(now);
		for(int i=head[now];~i;i=e[i].next){
			in[e[i].to]--;
			if(in[e[i].to]==0){
				q.push(e[i].to);
				sum++;
			}
		}
	}
	if(sum<n){
		cout<<"有环:"<<endl;
		print();
	}else cout<<"无环"<<endl; 
}

int t,c[maxn];
bool dfs(int x){
	c[x]=-1;//正在遍历中 
	for(int i=head[x];~i;i=e[i].next){
		if(c[e[i].to]==-1) return false;//存在环;
		else if(!c[e[i].to] && !dfs(e[i].to)) {ss.push(e[i].to);return false; }	
	}
	c[x]=1;//遍历结束 
	return true;
}
void dfs_topsort(){
	t=n;
	for(int i=1;i<=n;i++)
	if(!c[i] && !dfs(i)){
		cout<<"有环："<<endl;print();
		return; 
	}
	cout<<"无环"; 
}
int main(){
	init();
	bfs_topsort();//1 对应第一个测试样例
	
	dfs_topsort();//2 3 4 
	
	return 0;
}

/*两组测试数据：
1）有环
4 4
1 2
2 3
3 4
4 2
2）无环
12 16
1 2
1 3
2 3
1 4
3 5
4 5
11 6
5 7
3 7
3 8
6 8
9 10
9 11
9 12
10 12
1 12*/