拓扑排序.cpp

拓扑排序,VC能够通过,没错误!而且也比较好!

//拓扑排序
#include <iostream.h>
#include <stdlib.h>
const int MaxEdgeNum=100;
const int MaxVertexNum=100;
typedef int VertexType;
typedef int ElemType;
typedef VertexType vexlist[MaxVertexNum];//定义存储顶点信息的数组类型
struct edgenode{//定义邻接表中的边结点类型
	int adjvex;//邻接点域
	edgenode *next;
};
typedef edgenode *adjlist[MaxVertexNum];//定义存储N个表头指针的数组类型
bool visited[MaxVertexNum];
void Create(vexlist GV,adjlist GL,int v,int e)
{
	int i,j,k;
	cout<<"输入"<<v<<"个顶点:"<<endl;
	for(i=0;i<v;i++)
		cin>>GV[i];
	for(i=0;i<v;i++)
		GL[i]=NULL;
	cout<<"输入"<<e<<"条边:"<<endl;
	for(k=1;k<=e;i++)
	{
		cin>>i>>j;
		edgenode *p=new edgenode;//申请新结点
		p->adjvex=j;//将新结点插入到邻接表的表头
		p->next=GL[i];
		GL[i]=p;
	}
}
void Toposort(adjlist GL,int n)
{
	int i,j,k,top,m=0;
	edgenode *p;
	int *d=new int[n];
	for(i=0;i<n;i++)
		d[i]=0;
	for(i=0;i<n;i++)
	{
		p=GL[i];
		while(p!=NULL)
		{
			j=p->adjvex;
			d[j]++;
			p=p->next;
		}
	}
	top=-1;
	for(i=0;i<n;i++)
		if(d[i]==0)
		{
			d[i]=top;
			top=i;
		}
		while(top!=1)
		{
			j=top;
			top=d[top];
			cout<<j<<' ';
			m++;
			p=GL[j];
			while(p!=NULL)
			{
				k=p->adjvex;
				d[k]--;
				if(d[k]==0)
				{
					d[k]=top;
					top=k;
				}
				p=p->next;
			}
		}
		cout<<endl;
		if(m<n)
			cout<<"The network has a cycle!"<<endl;
}
void main()
{
	adjlist GL;
	vexlist GV;
	int v,e;
	cout<<"请输入顶点数：";
	cin>>v;
	cout<<"请输入边数：";
	cin>>e;
	Create(GV,GL,v,e);
	Toposort(GL,v);
}