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[] where TopOrder[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 case TopSort 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

#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; } bool TopSort( LGraph Graph, Vertex TopOrder[] ) { int a[MaxVertexNum]={0}; /*储存个点入度*/ int Queue[MaxVertexNum]; struct AdjVNode *p, *ptr; int j, top, front, rear; for( j=0; j<Graph->Nv; j++) { p=Graph->G[j].FirstEdge; if(p==NULL) break; } if(j>=Graph->Nv) { return false; } p=(struct AdjVNode *)malloc(sizeof(struct AdjVNode)); ptr=(struct AdjVNode *)malloc(sizeof(struct AdjVNode)); for(int i=0; i<Graph->Nv; i++) { p=Graph->G[i].FirstEdge; while(p!=NULL) { a[p->AdjV]=a[p->AdjV]+1; p=p->Next; } } top=0; front=rear=0; for(int i=0; i<Graph->Nv; i++) { p=Graph->G[i].FirstEdge; if(a[i]==0) { while(p!=NULL) { a[p->AdjV]--; p=p->Next; } a[i]=-2; Queue[rear++]=i; break; } } while(front!=rear) { TopOrder[top++]=Queue[front]; p=Graph->G[Queue[front++]].FirstEdge; while(p!=NULL) { if(a[p->AdjV]==0) { Queue[rear++]=p->AdjV; ptr=Graph->G[p->AdjV].FirstEdge; while(ptr!=NULL) { a[ptr->AdjV]--; ptr=ptr->Next; } } p=p->Next; } } return true; }