4-1 Topological Sort

Write a program to find the topological order in a digraph.

Format of functions:

bool TopSort( LGraph Graph, Vertex TopOrder[] );

where LGraph is defined as the following:

typedef struct AdjVNode *PtrToAdjVNode; struct AdjVNode{ Vertex AdjV; PtrToAdjVNode Next; };  

typedef struct Vnode{ PtrToAdjVNode FirstEdge;} AdjList[MaxVertexNum];typedef struct GNode *PtrToGNode;struct GNode{ int Nv; int Ne; AdjList G;};typedef PtrToGNode LGraph;

The topological order is supposed to be stored in TopOrder[] whereTopOrder[i] is the i-th vertex in the resulting sequence. The topological sort cannot be successful if there is a cycle in the graph -- in that caseTopSort must return false; otherwise return true.

Notice that the topological order might not be unique, but the judge's input guarantees the uniqueness of the result.

Sample program of judge:

#include <stdio.h> #include <stdlib.h> typedef enum {false, true} bool; #define MaxVertexNum 10 /* maximum number of vertices */ typedef int Vertex; /* vertices are numbered from 0 to MaxVertexNum-1 */ typedef struct AdjVNode *PtrToAdjVNode; struct AdjVNode{ Vertex AdjV; PtrToAdjVNode Next; }; typedef struct Vnode{ PtrToAdjVNode FirstEdge; } AdjList[MaxVertexNum]; typedef struct GNode *PtrToGNode; struct GNode{ int Nv; int Ne; AdjList G; }; typedef PtrToGNode LGraph; LGraph ReadG(); /* details omitted */ bool TopSort( LGraph Graph, Vertex TopOrder[] ); int main() { int i; Vertex TopOrder[MaxVertexNum]; LGraph G = ReadG(); if ( TopSort(G, TopOrder)==true ) for ( i=0; i<G->Nv; i++ ) printf("%d ", TopOrder[i]); else printf("ERROR"); printf("\n"); return 0; } /* Your function will be put here */

Sample Input 1 (for the graph shown in the figure):

5 7 1 0 4 3 2 1 2 0 3 2 4 1 4 2

Sample Output 1:

4 3 2 1 0

Sample Input 2 (for the graph shown in the figure):

5 8 0 3 1 0 4 3 2 1 2 0 3 2 4 1 4 2

Sample Output 2:

ERROR     bool TopSort( LGraph Graph, Vertex TopOrder[] ){ int begin=0,end=0; int i,k=0,c=0; int q[MaxVertexNum]; int indegree[MaxVertexNum]; PtrToAdjVNode a; for(i=0;i<MaxVertexNum;i++) //在pta里用{0}归零数组会报错，只能如此归零了 indegree[i]=0; for(i=0;i<Graph->Nv;i++) { //遍历节点初始化入度数组 a=Graph->G[i].FirstEdge; //G[i],就是每个结点的邻接表，a指向i顶点指向的下一个顶点 while(a!=NULL){ indegree[a->AdjV]++; //如果i顶点的下一个顶点存在，则此顶点入度减一 a=a->Next; } if(indegree[i]==0) //寻找入度为零的结点 q[end++]=i; } while(begin!=end){ //只有用队列才不超时 TopOrder[k++]=q[begin++]; a=Graph->G[q[begin-1]].FirstEdge; while(a!=NULL){ //更新a周围的顶点的入度并且找到为零的入队 indegree[a->AdjV]--; if(indegree[a->AdjV]==0) q[end++]=a->AdjV; a=a->Next; } } if(Graph->Nv!=k) //当队列为空的时候还有没入队的顶点 return false; return true; }