拓扑排序算法

[c]代码库

typedef struct vnode  /*顶点表结点*/
{
	int count /*存放顶点入度*/
	VertexType vertex; /*顶点域*/
	EdgeNode * firstedge; /*边表头指针*/
} VertexNode;

void Topo_Sort ( AlGraph *G )
{/*对以带入度的邻接链表为存储结构的图G，输出其一种拓扑序列*/
	int top = -1； /* 栈顶指针初始化*/
	          for ( i=0；i<n；i++ ) /* 依次将入度为0 的顶点压入链式栈*/
	{
		if ( G->adjlist[i]. Count = = 0 )
		{
			G->adjlist[i].count = top；
			                      top = i；
		                            }
	                            }
	                            for ( i=0; i<n; i++ )
	{
		if ( t0p= -1 )
		{
			printf ( “The network has a cycle” );
			return;
		}
		j=top;
		top=G->adjlist[top].count; /* 从栈中退出一个顶点并输出*/
		printf ( “% c”,G->adjlist[j].vertex );
		ptr=G->adjlist[j].firstedge;
		while ( ptr!=null )
		{
			k=ptr->adjvex;
			G->adjlist[k].count--; /*当前输出顶点邻接点的入度减1*/
			if ( G->adjlist[k].count= =0 ) /*新的入度为0 的顶点进栈*/
			{
				G->adjlist[k].count =top;
				top=k;
			}
			ptr=ptr->next; /*找到下一个邻接点*/
		}
	}
}