拓扑排序(C语言实现)

Touch_2011

对这个有向图进行拓扑排序
/* * 拓扑排序（采用邻接矩阵存储） */#include<stdio.h>#define MAX_VERTEX_NUM 20//图的定义typedef struct {int vertexNum;char vertex[MAX_VERTEX_NUM];int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM];}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[j]=0;g->arc[0][1]=1;g->arc[0][2]=1;g->arc[0][3]=1;g->arc[1][4]=1;g->arc[2][1]=1;g->arc[2][4]=1;g->arc[4][3]=1;g->arc[4][5]=1;}//拓扑排序void TopologicalSort(PGraph g){    int i,j,k=0,m;char vertex[MAX_VERTEX_NUM];while(k < g->vertexNum){//1.找没有入度的顶点,存入数组vertex中    for(i=0;i<g->vertexNum;i++){    for(j=0;j<g->vertexNum;j++){    if(g->arc[j]!=0)    break;}if(j==g->vertexNum){//检查g->vertex是否已经遍历for(m=0;m<k;m++)if(vertex[m]==g->vertex)break;if(m==k){        vertex[k++]=g->vertex;break;}}}//2.没有入度为0的顶点if(i==g->vertexNum){printf("存在回路!\n");return ;}//3.删除这个顶点的出度        for(j=0;j<g->vertexNum;j++)g->arc[j]=0;}//输出排序后的结果printf("拓扑排序结果：\n");for(i=0;i<k;i++)printf("%-3c",vertex);printf("\n");}void main(){Graph graph;createdGraph(&graph);TopologicalSort(&graph);}