拓扑排序 用dfs或者bfs
程序员文章站
2024-03-19 10:59:52
...
拓扑排序是找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*/