9-11.c

数据结构经典算法

#include "stdio.h"
#define MAX_VERTICES 100
typedef struct node *node_pointer;
typedef struct node { 
	int vertex;
	node_pointer link;
};
typedef struct  hd{  int count;
	node_pointer link;
} hdnodes;
hdnodes  graph[ MAX_VERTICES ];
void topsort(hdnodes graph[ ],int  n) 
{       int i,j,k,top;
        node_pointer ptr;
        /* create a stack of vertices with no predecessors*/
        top = -1;
        for (i = 0; i < n; i++)
           if (!graph[i].count){
               graph[i].count = top;
               top = i; 
           }   
        for (i = 0; i < n; i++)
           if (top = -1){    
              printf("网络存在循环，拓扑排序结束\n");
              exit(1);
           }
           else{
              j = top; /* unstack a vertex */
              top = graph[top].count;
              printf("v%d",j);
              for (ptr = graph[j].link; ptr; ptr = ptr->link){
              /*decrease the count of the successor vertices of j */
                 k = ptr->vertex;
                 graph[k].count--;
                 if ( !graph[k].count){ /* add vertex k to the stack */
                     graph[k].count = top;                  top = k;
                 }
              }
         }
}

void main(void)
{
	topsort(graph,10);
}