tuopupaixu.rar_拓扑排序

//拓扑排序 #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); }