【算法导论】邻接矩阵存储的拓扑排序-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

【算法导论】邻接矩阵存储的拓扑排序

简介:         在很多应用中,很多事情都是按照一定的次序来进行的,比如说起床穿衣时,不可能先穿鞋再穿袜子,但是穿袜子和穿裤子可以不分先后次序。这种按照一定顺序进行的活动,可以使用顶点表示活动,顶点之间的有向边表示活动间的先后关系,这种有向无回路图说明了活动的先后次序。

        在很多应用中,很多事情都是按照一定的次序来进行的,比如说起床穿衣时,不可能先穿鞋再穿袜子,但是穿袜子和穿裤子可以不分先后次序。这种按照一定顺序进行的活动,可以使用顶点表示活动,顶点之间的有向边表示活动间的先后关系,这种有向无回路图说明了活动的先后次序。

        当活动只能单个进行时,如果可以将图中的所有顶点排列成一个线性序列vi1, vi2, …, vin,并且这个序列同时满足关系:若从顶点vi到顶点vj存在一条路径,则在线性序列中vi必在vj之前,我们就称这个线性序列为拓扑序列。把对有向无回路图构造拓扑序列的操作称为拓扑排序。

其基本思想:

        拓扑排序的基本操作为:

1.从图中选择一个入度为0的顶点并且输出它;

2.从图中删除此顶点及所有由它发出的边;

3.重复上述过程,直到图中没有入度为0的边。

以上的操作会产生两种结果:一种是图中的全部顶点都被输出,整个拓扑排序完成;另一种是图中顶点未被全部输出,剩余的顶点的入度均不为0,则说明网中存在有向环。

上述表述比较抽象,下面我用图解的方式来介绍其思想:

假设有向无回路图如下所示:

依次删除入度为0的顶点的过程如下:

         

                                    a)输出A                                              b)输出B            

               

                                    c)输出D                                             d)输出C 


                                                                              

                                    e)输出E                                            f)输出F


因此得到的拓扑排序序列为: A B D C E F G.

具体的程序实现如下:

#include<stdio.h>
#include<stdlib.h>
#define N 7//顶点个数

typedef struct 
{
	char vexs[N];//顶点数组
	int arcs[N][N];//邻接矩阵
}graph;

void TopoSort_matrix(graph g)
{
	int row[N]={0};//按照列来设置标志,为1表示已经输出(不再考虑),为0表示未输出。
	int v=1;//标志符,1表示已经输出(不再考虑),为0表示未输出,赋给row数组
	int i,j,k,t,m;
	for(k=0;k<N;k++)
	{
		for(j=0;j<N;j++)
		{
			if(row[j]==0)//活动j还未输出
			{
				t=1;//标识符
				for(i=0;i<N;i++)
					if(g.arcs[i][j]==1)//当前活动有入度(活动i必须在活动j之前)
					{
						t=0;
						break;
					}
				if(t==1)//活动j没有入度
				{
					m=j;
					break;
				}
			}
		}
		if(j!=N)
		{
			row[m]=v;
			printf("%c",g.vexs[m]);
			for(i=0;i<N;i++)
				g.arcs[m][i]=0;//将已经输出的活动所到达的下个活动的入度置为0
			v++;
		}
		else 
			break;
		}
		if(v-1<N)//当row中不是所有的元素都被赋予新值v时,说明有环存在
			printf("\n该有向图有环存在!");
	
}

void main()
{
	graph g;
	int matrix[N][N]={{0,1,1,0,0,0,0},
					  {0,0,0,0,0,1,1},
			    	  {0,0,0,0,0,0,1},
					  {0,0,1,0,1,0,0},
					  {0,0,0,0,0,0,1},
					  {0,0,0,0,0,0,0},
					  {0,0,0,0,0,0,0}};
	char vertex[N]={'A','B','C','D','E','F','G'};//初始化
		for(int i=0;i<N;i++)
		{
			g.vexs[i]=vertex[i];
			for(int j=0;j<N;j++)
				g.arcs[i][j]=matrix[i][j];
		}
	TopoSort_matrix(g);
	printf("\n");
}

注:如果程序出错,可能是使用的开发平台版本不同,请点击如下链接: 解释说明

原文:http://blog.csdn.net/tengweitw/article/details/17265961

作者:nineheadedbird


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: