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

        上一篇文章中讲述了用邻接矩阵存储的图的拓扑排序，下面本文介绍用邻接表存储的图的拓扑排序。

        关于拓扑排序的概念及基本思想，我在上一篇文章中已经较为详细的描述了，这里不在介绍。我们知道利用邻接矩阵进行拓扑排序时，程序实现较为简单，但是效率不高，算法的复杂度为O(n^3).而利用邻接表会使入度为0的顶点的操作简化，从而提高算法的效率。

在邻接表存储结构中，为了便于检查每个顶点的入度，可在顶点表中增加一个入度域(id)，这样的邻接表如下图所示，这样只需对由n个元素构成的顶点表进行检查就能找出入度为0的顶点。为了避免对每个入度为0的顶点重复访问，可用一个链栈来存储所有入度为0的顶点。在进行拓扑排序前，只要对顶点表进行一次扫描，便可将所有入度为0的顶点都入栈，以后每次从栈顶取出入度为0的顶点，并将其输出。 

原始图为：

其对应的邻接表为：

在邻接表存储结构中实现拓扑排序算法的步骤为：
        (1) 扫描顶点表，将入度为0的顶点入栈。

        (2) 当栈非空时执行以下操作：

1.将栈顶顶点vi的序号弹出，并输出之；

2.检查vi的出边表，将每条出边表邻接点域所对应的顶点的入度域值减1，若该顶点入度为0，则将其入栈；

        (3) 若输出的顶点数小于n，则输出“有回路”，否则拓扑排序正常结束。
        在具体实现时，链栈无须占用额外空间，只需利用顶点表中入度域值为0的入度域来存放链栈的指针（即指向下一个存放链栈指针的单元的下标），并用一个栈顶指针top指向该链栈的顶部即可。由此给出以下的具体算法：

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

//邻接表的结构体
typedef struct Node
{
	int adjvex;
	struct Node *next;
}edgenode;

typedef struct
{
	char vertex;
	int id;
	edgenode *link;
}vexnode;

//进行拓扑排序
void TopoSort_AdjTable(vexnode ga[N])
{
	int i,j,k,m=0,top=-1;
	edgenode *p;
	for(i=0;i<N;i++)//将入度为0的顶点入栈
		if(ga[i].id==0)
		{
			ga[i].id=top;
			top=i;
		}
	while(top!=-1)//栈不为空
	{
		j=top;
		top=ga[top].id;//出栈
		printf("%c",ga[j].vertex);
		m++;
		p=ga[j].link;
		while(p)//删除该节点的所有出边
		{
			k=p->adjvex-1;
			ga[k].id--;
			if(ga[k].id==0)//将入度为0的顶点入栈
			{
				ga[k].id=top;
				top=k;
			}
			p=p->next;
		}
	}
	if(m<N)//当输出的顶点数小于N时，说明有环存在
		printf("该图存在环！");
}

void main()
{
	vexnode ga[N];
	char vertex[N]={'A','B','C','D','E','F','G'};
	int  ID[N]={0,1,2,0,1,1,3};
		for(int i=0;i<N;i++)
		{
			ga[i].vertex=vertex[i];
			ga[i].id=ID[i];
		}//初始化顶点表
		edgenode *s;
		
		//初始化边表
		s=(edgenode *)malloc(sizeof(edgenode));
		s->adjvex=2;
		ga[0].link=s;
		s=(edgenode *)malloc(sizeof(edgenode));
		s->adjvex=3;
		ga[0].link->next=s;
		s->next=NULL;

		s=(edgenode *)malloc(sizeof(edgenode));
		s->adjvex=6;
		ga[1].link=s;
		s=(edgenode *)malloc(sizeof(edgenode));
		s->adjvex=7;
		ga[1].link->next=s;
		s->next=NULL;


		s=(edgenode *)malloc(sizeof(edgenode));
		s->adjvex=7;
		ga[2].link=s;
		s->next=NULL;


		s=(edgenode *)malloc(sizeof(edgenode));
		s->adjvex=3;
		ga[3].link=s;
		s=(edgenode *)malloc(sizeof(edgenode));
		s->adjvex=5;
		ga[3].link->next=s;
		s->next=NULL;

		s=(edgenode *)malloc(sizeof(edgenode));
		s->adjvex=7;
		ga[4].link=s;
		s->next=NULL;

		ga[5].link=NULL;
		ga[6].link=NULL;
       //初始化边表结束
		TopoSort_AdjTable(ga);//进行拓扑排序
		printf("\n");


}

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

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

作者：nineheadedbird