c拓扑排序实例程序清单

1、程序清单：#includetypedef int VertexType;const int MaxVertexNum=20;/ 图的最大顶点数，它应不小于具体图的顶点数 n;const int MaxEdgeNum=30;/ 图的最大边数，它应不小于具体图的最大边数 e;typedef VertexType vexlistMaxVertexNum;/ 定义 vexlist 为存储顶点信息的数组 类型struct edgenode/ 定义邻接表中的边结点类型int adjvex;/ 邻接点域edgenode *next;/ 指向下一个边结点的链域;typedefedgenode*adjlistM

2、axVertexNum;/ 这义 adjlist 为存储 n 个表头指针 的数组类型voidCreate2(vexlistGV,adjlistGL,intn,inte) / 看看 GL 到底是什么： GLi-adjvex/通过从键盘上输入的n个顶点信息和e条有向边的信息/建立顶点数组GV和邻接表GLint i,j,k,w;/ 建立顶点数组cout输入n个顶点endl;for(i=0;iGVi;/ 初始化邻接表，即将表头向量中的每个域置空for(i=0;in;i+)GLi=NULL;/ 建立邻接表cout输入vvevv条边e ndl;for(k=1;k=e;k+)/ 输入一条边 cinij;/w

3、;/ 由系统分配一个新结点edgenode *p=new edgenode;/ 将 j 的值赋给新结点的邻接点域p-adjvex=j;/p-weight=w;/ 将新结点插入到 vi 邻接表的表头p-next=GLi;GLi=p;7voidToposort(adjlistGL,intn)/ 此算法的时间复杂度为 o(n+e)/n 为顶点数 ,e 为 边数/利用邻接表GL表示的有向图进行拓朴排序int i,j,k,top,m=0;/m 用来统计拓朴序列中的顶点/top 的值为一个入度为 0的顶点序号， top 指向的值为下一个入度为 0的 顶点序号edgenode *p;/ 定义存储图中每个顶点

4、入度的一维整型数组 dint *d=new intn;/ 初始化数组 d 中的每个元素值为 0for(i=0;in;i+)di=0;/ 利用数组 d 中的对应元素统计出每个顶点的入度for(i=0;iadjvex;dj+;p=p-next;top 为-1/ 初始化用于链接入度为 0 的元素的栈的栈顶指针 top=-1;/ 建立初始化栈for(i=0;in;i+)if(di=0)di=top;top=i;/ 每循环一次删除一个顶点及所有出边cout 拓朴序列如下 :endl; while(top!=-1)j=top;/j 的值为一个入度为 0 的顶点序号 top=dtop;/ 删除栈顶点元素 coutjadjvex;/vk 是 vj 的一个邻接点dk-;/vk 的入度减 1 if(dk=0)/ 把入度为 0 的元素进栈dk=top; top=k;p=p-next;/p 指向 vj 邻接点表的下一个结点 coutendl;(拓朴图是if(mn)/ 当输出的顶点数小于图中的顶点数时，输出有回路信息 无回路的，因/ 为若带有回路，则回路上的所有活动都无法进行 )coutThe network has a cycle!endl;void main()vexlist GV;adjlist GL;int