使用C++语言BFS实现拓扑排序，BFS和DFS实现逆拓扑排序

目录

1.有向无环图

2.拓扑排序

（1）拓扑排序实现步骤

（2）逆拓扑排序的实现步骤

---

1.有向无环图

有向无环图：一个无环的有向图。简称DAG图。

有向无环图的应用：描述一项工程或系统的进行过程。由于几乎所有的工程都可分为若干个称为活动的子工程，而这些子工程之间也是存在约束的，比如某些子工程的开始必须在另外一些子工程完成之后才能进行。对于要完成的工程来说就是该工程能否顺利的进行和工程完成的最短时间。而有向无环图即可应用于此。

2.拓扑排序

由一个有向无环图的顶点组成的序列，当且仅当满足以下条件：

     a.每个顶点只能出现一次；

     b.若顶点A在序列中排在顶点B之前，那么B不能出现在A之前，也就是不能出现环；

（1）拓扑排序实现步骤

第一步：从AOV网中选择一个没有前驱（也就是入度为0的顶点）的顶点并输出；

第二步：从网络中删除顶点和所有以它为起点的有向边；

第三步：重复以上的操作，直到当前网络中不存在无前驱的顶点为止。

注：AOV网：使用顶点表示活动，用弧表示活动之间的优先关系的有向图称为顶点表示活动的网络（Activity On Vertex Network）——AOV网。在网络中。若从顶点i到顶点j有一条有向路径，则i是j的前驱；j是i的后继。若是网络中一条弧，则i是j的直接前驱；j是i的直接后继。也就是AOV网络不能存在环，因为活动之间是有某种先后顺序关系的。

 如上图所示：当前网络中入度为0的只有顶点a,所以首先输出的顶点为a.

#include<stdio.h>
#include<queue>
#include<stdlib.h>
 
#define maxn 10
#define inf 0x3f3f3f3f
using namespace std;
 
int n,m;
//保存入度 
int indegree[maxn];
//保存边 
int edge[maxn][maxn];
//保存输出的拓扑排序
int output[maxn]; 
 
void init(){
	for(int i=0;i<maxn;i++){
		indegree[i]=0;
		output[i]=0;
		for(int j=0;j<maxn;j++){
			edge[i][j]=0;
		}
	}
} 
 
void TopoSort(){
	queue<int>q;
	int count=0;
	for(int i=1;i<=n;i++){
		if(indegree[i]==0){
			q.push(i);
		}
	}
	int k=1;
	while(!q.empty()){
		int v=q.front();
		count++;
		q.pop();
		output[k++]=v;
		for(int i=1;i<=n;i++){
			if(i!=v&&edge[v][i]){
				indegree[i]--;
				if(indegree[i]==0){
					q.push(i);
				}
			}
		}
	}
	if(count==n){
		for(int i=1;i<n;i++){
			printf("%d->",output[i]);
		}
		printf("%d\n",output[n]);
	}else{
		printf("存在环!\n");
	}
}
 
int main(){
    init();
	printf("请输入顶点数: ");
	scanf("%d",&n);
	printf("请输入边数: ");
	scanf("%d",&m);
	printf("请输入边: \n");
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d %d",&u,&v);
		indegree[v]++;
		edge[u][v]=1;
	}
	TopoSort();
	return 0;
}
/*
6 6
 
1 2 
1 3
2 4 
2 5
3 6
6 4
*/

（2）逆拓扑排序的实现步骤

第一步：从AOV网络中选择一个没有后继（出度为0）的顶点并输出；

第二步：从网络中删除该顶点和所有以它为终点的有向边；

第三步：重复上述操作，直至AOV网络为空。

注：具体的画图和上面是类似的，只是从出度为0的顶点开始而已（相反的操作）。

 方式一：使用BFS输出逆拓扑排序

#include<stdio.h>
#include<queue>
#include<stdlib.h>
 
#define maxn 10
#define inf 0x3f3f3f3f
using namespace std;
 
int n,m;
//保存入度 
int outdegree[maxn];
//保存边 
int edge[maxn][maxn];
//保存输出的拓扑排序
int output[maxn]; 
 
void init(){
	for(int i=0;i<maxn;i++){
		outdegree[i]=0;
		output[i]=0;
		for(int j=0;j<maxn;j++){
			edge[i][j]=0;
		}
	}
} 
 
void TopoSort(){
	queue<int>q;
	int count=0;
	for(int i=1;i<=n;i++){
		if(outdegree[i]==0){
			q.push(i);
		}
	}
	int k=1;
	while(!q.empty()){
		int v=q.front();
		count++;
		q.pop();
		output[k++]=v;
		for(int i=1;i<=n;i++){
			if(i!=v&&edge[i][v]){
				outdegree[i]--;
				if(outdegree[i]==0){
					q.push(i);
				}
			}
		}
	}
//	printf("%d\n",count);
	if(count==n){
		for(int i=1;i<n;i++){
			printf("%d->",output[i]);
		}
		printf("%d\n",output[n]);
	}else{
		printf("存在环!\n");
	}
}
 
int main(){
    init();
	printf("请输入顶点数: ");
	scanf("%d",&n);
	printf("请输入边数: ");
	scanf("%d",&m);
	printf("请输入边: \n");
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d %d",&u,&v);
		outdegree[u]++;
		edge[u][v]=1;
	}
	TopoSort();
	return 0;
}
/*
6 6
 
1 2 
1 3
2 4 
2 5
3 6
6 4
*/

 方式二：使用DFS输出拓扑排序

#include<stdio.h>
#include<queue>
#include<stdlib.h>
 
#define maxn 10
#define inf 0x3f3f3f3f
using namespace std;
 
int n,m;
//保存出度 
int outdegree[maxn];
bool vis[maxn];
//保存边 
int edge[maxn][maxn];
//保存输出的拓扑排序
int output[maxn]; 
int k=1;
 
void init(){
	for(int i=0;i<maxn;i++){
		vis[i]=false;
		outdegree[i]=0;
		output[i]=0;
		for(int j=0;j<maxn;j++){
			edge[i][j]=0;
		}
	}
} 
 
void DFS(int u){
	for(int i=1;i<=n;i++){
		//访问到当前的顶点时，如果存在出度，那么首先减一 
		if(outdegree[u]>0){
			outdegree[u]--;
		}
		if(vis[i]==false){
			if(i!=u&&edge[u][i]){
				DFS(i);	
			}
		}	
	}
	//这一段主要是为了判断出度是否为0 
	if(outdegree[u]==0){
		output[k++]=u;
		vis[u]=true;
	}else{
		//出栈的时候，前面是已经入栈的，并且也已经是首先减一的
		//所以前面已经出栈的表示已经访问了，因此和出栈的顶点之间的边需要断开
		//所以需要进行outdegree[u]-- 
		outdegree[u]--;
		if(outdegree[u]==0){
			output[k++]=u;
			vis[u]=true;
		}
	}
} 
 
void DFSTopoSort(){
	for(int i=1;i<=n;i++){
		if(vis[i]==false){
			DFS(i);
		}
	}
	for(int i=1;i<n;i++){
		printf("%d->",output[i]);
	}
	printf("%d\n",output[n]);
}
 
 
int main(){
	init();
	printf("请输入顶点数: ");
	scanf("%d",&n);
	printf("请输入边数: ");
	scanf("%d",&m);
	printf("请输入边: \n");
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d %d",&u,&v);
		edge[u][v]=1;
		outdegree[u]++;
	}
	DFSTopoSort();
	return 0;
}
/*
6 6
 
1 2 
1 3
2 4 
2 5
3 6
6 4
 
6 5
 
1 2
1 3
1 4
1 5
1 6
*/