拓扑排序 代码 C语言

《拓扑排序 代码 C语言》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、/*用邻接表表示图的拓扑排序算法*/#include#include#defineMAXVEX100#defineTRUE1#defineFALSE0typedefstructEdgeNodeEdgeNode;typedefstructEdgeNode*PEdgeNode;typedefstructEdgeNode*EdgeList;structEdgeNode{intendvex;/*相邻顶点字段*/PEdgeNodenextedge;/*链字段*/};/*边表中的结点*/typedefstruc

2、t{/*VexTypevertex;*//*顶点信息*/EdgeListedgelist;/*边表头指针*/}VexNode;/*顶点表中的结点*/typedefstruct{intn;/*图的顶点个数*/VexNodevexs[MAXVEX];}GraphList;typedefstruct{intvexsno[MAXVEX];/*顶点在顶点表中的下标值*//*VexTypevexs[MAXVEX];*//*顶点信息*/}Topo;/*求出图中所有顶点的入度*//*方法是搜索整个邻接表*/voidfindInDegree(GraphL

3、ist*g,int*inDegree){inti;PEdgeNodep;for(i=0;in;i++)inDegree[i]=0;for(i=0;in;i++){p=g->vexs[i].edgelist;while(p){++inDegree[p->endvex];p=p->nextedge;}}}inttopoSort(GraphList*paov,Topo*ptopo){EdgeListp;inti,j,k,nodeno=0,top=-1;intindegree[MAXVEX];findInDegree(paov,

4、indegree);/*求出图中所有顶点的入度*/for(i=0;in;i++)if(indegree[i]==0){/*将入度为零的顶点入栈*/indegree[i]=top;top=i;}while(top!=-1){/*栈不为空*/j=top;top=indegree[top];/*取出当前栈顶元素*/ptopo->vexsno[nodeno++]=j;p=paov->vexs[j].edgelist;/*取该元素边表中的第一个边结点*/while(p){/*删除以该顶点为起点的边*/k=p->endvex;inde

5、gree[k]--;if(indegree[k]==0){/*将新的入度为零的边入栈*/indegree[k]=top;top=k;}p=p->nextedge;}}if(nodenon){/*AOV网中存在回路*/printf("Theaovnetworkhasacycle");returnFALSE;}returnTRUE;}/*边的插入算法*/voidinsert(GraphList*p,inta,intb){EdgeListpp;PEdgeNodetemp;temp=(PEdgeNode)malloc(size

6、of(EdgeNode));temp->endvex=b;temp->nextedge=NULL;pp=p->vexs[a].edgelist;if(pp==NULL)p->vexs[a].edgelist=temp;else{while(pp->nextedge!=NULL)pp=pp->nextedge;pp->nextedge=temp;}}/*实例邻接表的构造*/GraphList*makeList(){GraphList*p;inti;p=(GraphList*)malloc(sizeof(GraphList));p->n=9

7、;for(i=0;in;i++)p->vexs[i].edgelist=NULL;insert(p,0,2);insert(p,0,7);insert(p,1,2);insert(p,1,3);insert(p,1,4);insert(p,2,3);insert(p,3,5);insert(p,3,6);insert(p,4,5);insert(p,7,8);insert(p,8,6);returnp;}voidmain(){GraphList*p;Topotopo;inti;p=makeList();if(topoSort(p

8、,&topo)==TRUE){printf("邻接表表示图的拓扑排序结果如下：");for(i=0;in;i++)printf("%d",topo.vexsno[i]);}printf(""