topol_order.cpp

C++的电子教程

//程序实例8_8
//拓扑排序
#include<stdio.h>
#include<stdlib.h>
#define Max 50

typedef struct e_node
{	int adjvex;
	struct e_node *next;
}E_node;

typedef struct v_node
{	int count;
	E_node *link;
}V_node;

V_node head[Max];
int tpv[Max];

//邻接表的建立
void adjlist(V_node head[],int n,int m)  //n=顶点数，m=边数
{	int i,u,v;
	E_node *p;
	for(i=1;i<=n;i++)       //顶点结点初始化
	{	head[i].link=NULL;
		head[i].count=0;   
	}
	for(i=1;i<=m;i++)
	{	
		printf("Input Edge %d's start point : ",i);
		scanf("%d",&u);
		printf("==> end point : ");
		scanf("%d",&v);
		if((v>n) || (u>n))
		{	printf("Error! Input again.");
			continue;
		}
		p=(E_node *)malloc(sizeof(E_node));  //新结点存放w
		p->adjvex=v;    //终点为w的边结点链到第v个链表
		p->next=head[u].link;
		head[u].link=p;
		(head[v].count)++;
	    printf("Edge %d : (v%d,v%d)\n",i,u,v);  //输出第i条边
	}
}

int topol(V_node adj[],int n,int tpv[])    //tpv用来存放拓扑序列
{
	int i,j,k,top=0;
	E_node *t;
	for(i=1;i<=n;i++)   //建立入度为0的顶点的堆栈
		if(adj[i].count==0)
		{   adj[i].count=top;
			top=i;
		}

	i=0;    //i为已加入拓扑序列的顶点个数
	while(top!=0)   //出栈、入栈操作
	{	j=top;
		top=adj[top].count;
		tpv[++i]=j;

		t=adj[j].link;   //取邻接表第j个链表表头结点
		while(t!=NULL)
		{	k=t->adjvex;              //取顶点值
			if(--(adj[k].count)==0)   //顶点k的入度减1后为0
			{	adj[k].count=top;     //顶点k进栈
				top=k;
			}
			t=t->next;    //顶点j的下一个后继顶点
		}
	}
	return(i);     //返回边数
}

//主函数
void main()
{
	int n,m;
	printf("\n 请输入有向图的顶点数n、边数m的值：");
	scanf("%d %d",&n,&m);
	printf("\n邻接表的建立：");
    adjlist(head,n,m);

    int count=topol(head,n,tpv);

	if (count<n)
		printf("图中存在回路!\n");
	else
	{
		printf("拓扑序列为: ");
		for (int i=1;i<=n;i++)
			printf("%4d",tpv[i]);
		printf("\n");
	}
}