首页 > 其他 > 详细

数据结构:图论:拓扑排序! 两种方法!

时间:2014-06-10 14:22:23      阅读:356      评论:0      收藏:0      [点我收藏+]

拓扑排序:(1)由偏序变成全序的过程!直观的说,偏序指集合中仅有部分成员之间可比较!而全序指集合中全体成员之间均可比较!

                    (2)将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。

数据结构中进行拓扑排序的方法:

方法一:

(1)在有向图中选一个没有前驱的顶点且输出之!

(2)从图中删除该顶点和所有以它为尾的弧。

(3)重复上述两部,直至全部顶点均已输出,或者当前图中不存在无前驱的顶点为止。后一种情况说明有向图中存在环!

代码:

#include <iostream>
#include <string>
using namespace std;

const int MAXN = 1000;
int G[MAXN][MAXN], n, m, count = 0;   //n代表DAG中的顶点的个数,m代表DAG中的边的个数!
int ans[MAXN];

bool topoSort(int a[][MAXN]) {
	int into[MAXN];   //记录所有顶点的入度。
	memset(into, 0, sizeof(into));
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) {
			if(a[i][j])  ++into[j]; //求出图中所有顶点的入度!
		}
	}
	for(int i = 0; i < n; ++i) {  //循环n次,每一次加入一个点到拓扑排序中去!
		int j = 0;
		while(into[j] != 0) {  //寻找图中入度为零的点!
			++j;
			if(j >= n) return false;  //DAG中存在有向环!
		}
		ans[i] = j;  //把该入度为零的点放入拓扑排序中!
		into[j] = -1;   //该点放进拓扑排序以后,把他的入度标记为-1,为了下一次找入度为零的点做准备!
		for(int k = 0; k < n; ++k) {    //没加入一个点到拓扑排序中以后,更新各顶点的入度!
			if(a[j][k])  --into[k];
		}
	}
	return true;
}

int main() {
	cin >> n >> m;
	memset(G, 0, sizeof(G));
	for(int i = 0; i < m; ++i) {
		int u, v;
		cin >> u >> v;
		G[u][v] = 1;
	}
	if(topoSort(G))	{
		for(int i = 0; i < n; ++i) {
			cout << ans[i] << " ";
		}
		cout << endl;
	}else {
		cout << "can not topoSort, because DAG has a circle" << endl;
	}
	return 0;
}


 

方法二:

当有向图中无环的时候,可以利用dfs来进行拓扑排序。因为图中无环,则由图中某点出发进行DFS时,最先退出DFS函数的顶点即出度为零的点,是拓扑排序中最后一个顶点。所以按退出DFS函数的先后记录下来的顶点序列即为逆向的拓扑有序序列。

 

下面的代码中:c[u]==0 代表该点u从来没有调用过dfs(u),c[u]==1则代表递归调用过dfs(u)和u的所有子孙,c[u]==-1 代表该点u正在调用dfs(u)(即递归调用dfs(u)正在栈帧中,尚未返回)。

 

#include <iostream>
#include <string>
using namespace std;

const int MAXN = 1000;
int n, m, t;
int G[MAXN][MAXN], c[MAXN];

bool dfs(int u) {
	c[u] = -1;   //开始递归调用u节点,所以设置c[u] = -1;
	for(int v = 0; v < n; ++v) if(G[u][v]){
		if(c[v] < 0) return false;      //如果u的一个子孙节点v正在调用中,说明该DAG存在有向环,则返回false
		else if(!c[v] && !dfs(v)) return false   //如果u的一个子孙节点v从来没调用过,但是v的子树中存在有向环,则返回false
	}
	c[u] = 1;   //检查完了u节点的所有子孙,中途没有返回false,说明u的子树中不存在有向环
	topo[--t] = u;  //所以把该节点加入到拓扑排序中
	return true;
}

bool topoSort() {
	t = n;
	memset(c, 0, sizeof(c));
	for(int u = 0; u < n; ++i)  if(!c[u]){    //如果该节点u从来没有递归调用过
		if(!dfs(u)) return false;     //如果该节点u的所有子树中存在有向环,则返回false
	}
	return true;
}

int main() {
	cin >> n >> m;
	memset(G, 0, sizeof(G));
	for(int i = 0; i < m; ++i) {
		int u, v;
		cin >> u >> v;
		G[u][v] = 1;
	}
	if(topoSort()){
		for(int i = 0; i < n; ++i){
			cout << topo[i] << " ";
		}
		cout << endl;
	}else{
		cout << "can not topoSort, because DAG has a circle" << endl;
	}
	return 0;
}


 

数据结构:图论:拓扑排序! 两种方法!,布布扣,bubuko.com

数据结构:图论:拓扑排序! 两种方法!

原文:http://blog.csdn.net/u010470972/article/details/29568109

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!