拓扑排序.cpp

共有10个文件代码

#include<iostream.h>
#include<malloc.h>
#define Vnum 20
typedef struct arcnode   //边结构
{
	int adjvex;
	struct arcnode *next;
}arcnode;
typedef struct vexnode   //结点结构
{
	int vexdata;
	int in;
	arcnode *firstarc;
}adjlist[Vnum];
typedef struct graphs   //图结构
{
	adjlist adjlist;
	int vexnum,arcnum;
}graph;
void create(graph *g)
{
	int n,e,i,j,k;
	arcnode *p;
	cout<<"创建一个图:"<<endl;
	cout<<"顶点数:";
	cin>>n;
	cout<<"边数:";
	cin>>e;
	g->vexnum=n;g->arcnum=e;
	for(i=0;i<n;i++)
	{
		g->adjlist[i].vexdata=i;
		g->adjlist[i].firstarc=NULL;
	}
	for(k=0;k<e;k++)
	{
		cout<<"第"<<k+1<<"条边(节点从0到"<<n-1<<")";
		cin>>i>>j;
		p=(arcnode *)malloc(sizeof(arcnode));
		p->adjvex=j;
		p->next=g->adjlist[i].firstarc;  //将p插到adjlist[i]链表的前面；
		g->adjlist[i].firstarc=p;
	}
}
void disp(graph *g)
{
	int have,i;
	arcnode *p;
	cout<<"输出图:"<<endl;
	for(i=0;i<g->vexnum;i++)
	{
		p=g->adjlist[i].firstarc;
		have=0;
		while(p!=NULL)
		{
			cout<<"("<<i<<","<<p->adjvex<<")";
			p=p->next;
			have=1;
		}
		if(have==1)
			cout<<endl;
	}
}
void topsort(graph *g)
{
	int top,m,k,j,s[20];
	arcnode *p;
	top=0;m=0;
	for(j=0;j<g->vexnum;j++)
	{
		if(g->adjlist[j].in==0)  //入度为0时进栈
			s[top++]=j;
	}
	while(top>0)
	{
		j=s[--top];
		cout<<g->adjlist[j].vexdata<<" ";
		m++;
		p=g->adjlist[j].firstarc;
		while(p!=NULL)
		{
			k=p->adjvex;
			g->adjlist[k].in--;
			if(g->adjlist[k].in==0)
				s[top++]=k;
			p=p->next;
		}
	}
	cout<<endl;
	cout<<"输出的顶点个数:"<<m<<endl;
	if(m<g->vexnum)
		cout<<"此图拥有环"<<endl;
}
void main()
{
	
	graph g;
	create(&g);
	disp(&g);
	cout<<"拓扑排序为:";
	topsort(&g);
	cout<<endl;
}