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,int d[][2])  //n=顶点数，m=边数
{	int i;
	E_node *p;
	for(i=1;i<=n;i++)       //顶点结点初始化
	{	head[i].link=NULL;
		head[i].count=0;   
	}
	for(i=1;i<=m;i++)
	{	
		p=(E_node *)malloc(sizeof(E_node));  //新结点存放w
		p->adjvex=d[i-1][1];    //终点为w的边结点链到第v个链表
		p->next=head[d[i-1][0]].link;
		head[d[i-1][0]].link=p;
		(head[d[i-1][1]].count)++;
	}
}

//输出邻接表
void Print(V_node head[],int n)
{	int i;
	E_node *p;
	for(i=1;i<=n;i++)
	{	printf("\nhead[%d]:%d",i,head[i].count);
		if(head[i].link)
		{	p=head[i].link;
			while(p)
			{
				printf("->[%d]",p->adjvex);
				p=p->next;
			}
		}
		printf("\n");
	}
	printf("\n");
}

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=9,m=11;
	int dat[][2]={{1,8},{1,3},{2,3},{2,5},{8,9},{3,4},{5,4},{5,6},
					{9,7},{4,7},{4,6}};

	printf("\n邻接表为：");
    adjlist(head,n,m,dat);
	Print(head, n);

    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");
	}
}