拓扑排序-ag真人游戏

一个无环的有向图称为无环图（directed acyclic graph），简称dag图。

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称之为aov网（active on vertex network）。

拓扑序列：设g=(v,e)是一个具有n个顶点的有向图，v中的顶点序列v1,v2,……,vn满足若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前。则我们称这样的顶点序列为一个拓扑序列。

现在举个例子，如下图所示:

其中拓扑图如下：

可以做邻接矩阵

下面是代码：

// 边表结点声明
typedef struct edgenode
{
	int adjvex;
	struct edgenode *next;
}edgenode;
// 顶点表结点声明
typedef struct vertexnode
{
	int in;			// 顶点入度
	int data;
	edgenode *firstedge;
}vertexnode, adjlist[maxvex];
typedef struct
{
	adjlist adjlist;
	int numvertexes, numedges;
}graphadjlist, *graphadjlist;
// 拓扑排序算法
// 若gl无回路，则输出拓扑排序序列并返回ok，否则返回error
status topologicalsort(graphadjlist gl)
{
	edgenode *e;
	int i, k, gettop;
	int top = 0;		// 用于栈指针下标索引
	int count = 0;		// 用于统计输出顶点的个数
	int *stack;			// 用于存储入度为0的顶点
	
	stack = (int *)malloc(gl->numvertexes * sizeof(int));
	
	for( i=0; i < gl->numvertexes; i   )
	{
		if( 0 == gl->adjlist[i].in )
		{
			stack[  top] = i;	// 将度为0的顶点下标入栈
		}
	}
	
	while( 0 != top )
	{
		gettop = stack[top--];	// 出栈
		printf("%d -> ", gl->adjlist[gettop].data);
		count  ;				
		
		for( e=gl->adjlist[gettop].firstedge; e; e=e->next )
		{
			k = e->adjvex;
			// 注意：下边这个if条件是分析整个程序的要点！
			// 将k号顶点邻接点的入度-1，因为他的前驱已经消除
			// 接着判断-1后入度是否为0，如果为0则也入栈
			if( !(--gl->adjlist[k].in) )	
			{
				stack[  top] = k;
			}
		}
	}
	
	if( count < gl->numvertexes )	// 如果count小于顶点数，说明存在环
	{
		return error;
	}
	else
	{
		return ok;
	}
}