拓扑排序(C语言实现)
http://dl.iteye.com/upload/attachment/496407/1cd4c52f-a1a3-343a-801d-27702406c0ae.jpg对这个有向图进行拓扑排序
/* * 拓扑排序（采用邻接矩阵存储） */#include<stdio.h>#define MAX_VERTEX_NUM 20//图的定义typedef struct {int vertexNum;char vertex;int arc;}Graph,*PGraph;//构造有向图void createdGraph(PGraph g){int i,j; g->vertexNum=6; for(i=0;i<g->vertexNum;i++)g->vertex='A'+i;for(i=0;i<g->vertexNum;i++)for(j=0;j<g->vertexNum;j++) g->arc=0;g->arc=1;g->arc=1;g->arc=1;g->arc=1;g->arc=1;g->arc=1;g->arc=1;g->arc=1;}//拓扑排序void TopologicalSort(PGraph g){ int i,j,k=0,m;char vertex;while(k < g->vertexNum){//1.找没有入度的顶点,存入数组vertex中 for(i=0;i<g->vertexNum;i++){ for(j=0;j<g->vertexNum;j++){ if(g->arc!=0) break;}if(j==g->vertexNum){//检查g->vertex是否已经遍历for(m=0;m<k;m++)if(vertex==g->vertex)break;if(m==k){ vertex=g->vertex;break;}}}//2.没有入度为0的顶点if(i==g->vertexNum){printf("存在回路!\n");return ;}//3.删除这个顶点的出度 for(j=0;j<g->vertexNum;j++)g->arc=0;}//输出排序后的结果printf("拓扑排序结果：\n");for(i=0;i<k;i++)printf("%-3c",vertex);printf("\n");}void main(){Graph graph;createdGraph(&graph);TopologicalSort(&graph);}
页:
[1]