第13周项目5-拓扑排序算法的验证

问题：

[cpp]  view plain  copy /*  * Copyright (c)2016,烟台大学计算机与控制工程学院  * All rights reserved.  * 文件名称：项目5.cbp  * 作    者：程德泉  * 完成日期：2016年12月2日  * 版 本 号：v1.0    * 问题描述：拓扑排序算法的验证    * 输入描述：无  * 程序输出：测试数据  */   头文件及功能函数详见 【图算法库】

代码：

[cpp]  view plain  copy #include "graph.h"         void TopSort(ALGraph *G)   {       int i,j;       int St[MAXV],top=-1;            //栈St的指针为top       ArcNode *p;       for (i=0; i<G->n; i++)          //入度置初值0           G->adjlist[i].count=0;       for (i=0; i<G->n; i++)          //求所有顶点的入度       {           p=G->adjlist[i].firstarc;           while (p!=NULL)           {               G->adjlist[p->adjvex].count++;               p=p->nextarc;           }       }       for (i=0; i<G->n; i++)           if (G->adjlist[i].count==0)  //入度为0的顶点进栈           {               top++;               St[top]=i;           }       while (top>-1)                  //栈不为空时循环       {           i=St[top];           top--;              //出栈           printf("%d ",i);            //输出顶点           p=G->adjlist[i].firstarc;   //找第一个相邻顶点           while (p!=NULL)           {               j=p->adjvex;               G->adjlist[j].count--;               if (G->adjlist[j].count==0)//入度为0的相邻顶点进栈               {                   top++;                   St[top]=j;               }               p=p->nextarc;       //找下一个相邻顶点           }       }   }         int main()   {       ALGraph *G;       int A[10][10]=       {           {0,0,0,1,1,0,0,0,0,1},           {0,0,1,1,0,0,0,1,0,0},           {0,0,0,0,1,1,0,0,1,0},           {0,0,0,0,0,0,1,0,0,0},           {0,0,0,0,0,0,0,1,0,0},           {0,0,0,0,1,0,0,0,0,0},           {0,0,0,0,0,0,0,0,0,0},           {0,0,0,0,0,0,1,0,0,0},           {0,0,0,0,0,0,0,0,0,1},           {0,0,0,0,0,0,0,0,0,0}       };       ArrayToList(A[0], 10, G);       DispAdj(G);       printf("\n");       printf("拓扑序列:");       TopSort(G);       printf("\n");       return 0;   }  

测试用图：

运行结果：

知识点总结： 拓扑排序算法的验证。