拓扑排序------C++

1、题目14拓扑排序1、问题描述拓扑排序可判断AOV网络中是否存在回路，使的所有活动可排成一个线性序列，使用每个活动的所有前驱活动都排在该活动的前面。2、要求(1)在有向图中选一个没有前驱的顶点，输出；(2)从有向图中删除该顶点及其该顶点出发的所有边；(3)重复以上两个步骤，直至全部顶点输出；注：输出所有拓扑排序可加分。#include#includeusingnamespacestd;structedgenode/邻接表中的边节点类型intadjvex;edgenode*next;classGAdjoinpublic:voidInitAdjoin();/初始化图voidCreateAdjoin(

2、);/创建图的邻接表voidPrintAdjoin();/输出图的邻接表voidToposort();/输出图的拓扑序列private:intMaxValue;intVertexNum;intEdgeNum;boolvisited50;edgenode*adjlist50;edgenode*p;创建图的邻接表初始化图voidGAdjoin:InitAdjoin()intv,e;coutendl;coutv;VertexNum=v;coutendl;for(inti=0;i=v;i+)adjlisti=NULL;coute;EdgeNum=e;voidGAdjoin:CreateAdjoin()

3、intfromvex,endvex,e;coutendl;for(e=0;eEdgeNum;e+)cout请输入第e+1fromvexendvex;p=newedgenode;p-adjvex=endvex;p-next=adjlistfromvex;adjlistfromvex=p;/输出图的邻接表voidGAdjoin:PrintAdjoin()for(inti=0;iVertexNum;i+)coutvi;p=adjlisti;while(p!=NULL)coutadjvex;p=p-next;coutendl;/输出图的拓扑序列voidGAdjoin:Toposort()inti,j,

4、k,top,m=0;edgenode*p;int*d=newintVertexNum;for(i=0;iVertexNum;i+)di=0;for(i=0;iadjvex;dj+;p=p-next;)top=-1;for(i=0;iVertexNum;i+)if(di=0)di=top;top=i;)while(top!=-1)j=top;top=dtop;coutj;m+;p=adjlistj;while(p!=NULL)k=p-adjvex;dk-;if(dk=0)dk=top;top=k;)p=p-next;)coutendl;if(mVertexNum)coutThenetworkhasacycle!endl;coutendl;)voidmain()(GAdjoingl;cout建立图的邻接表endl;gl.InitAdjoin();gl.CreateAdjoin(