// algo7-4.cpp 輸出有向圖的一個拓撲序列。實現算法7.12的程序
 #include"c1.h"
 #define MAX_NAME 5 // 頂點字符串的最大長度
 typedef int InfoType;
 typedef char VertexType[MAX_NAME]; // 字符串類型
 #include"c7-2.h"
 #include"bo7-2.cpp"

 void FindInDegree(ALGraph G,int indegree[])
 { // 求頂點的入度，算法7.12、7.13調用
   int i;
   ArcNode *p;
   for(i=0;i<G.vexnum;i++)
     indegree[i]=0; // 賦初值
   for(i=0;i<G.vexnum;i++)
   {
     p=G.vertices[i].firstarc;
     while(p)
     {
       indegree[p->adjvex]++;
       p=p->nextarc;
     }
   }
 }

 typedef int SElemType; // 棧類型
 #include"c3-1.h"
 #include"bo3-1.cpp"
 Status TopologicalSort(ALGraph G)
 { // 有向圖G采用鄰接表存儲結構。若G無回路,則輸出G的頂點的一個拓撲序列并返回OK,
   // 否則返回ERROR。算法7.12
   int i,k,count,indegree[MAX_VERTEX_NUM];
   SqStack S;
   ArcNode *p;
   FindInDegree(G,indegree); // 對各頂點求入度indegree[0..vernum-1]
   InitStack(S); // 初始化棧
   for(i=0;i<G.vexnum;++i) // 建零入度頂點棧S
     if(!indegree[i])
       Push(S,i); // 入度為0者進棧
   count=0; // 對輸出頂點計數
   while(!StackEmpty(S))
   { // 棧不空
     Pop(S,i);
     printf("%s ",G.vertices[i].data); // 輸出i號頂點并計數
     ++count;
     for(p=G.vertices[i].firstarc;p;p=p->nextarc)
     { // 對i號頂點的每個鄰接點的入度減1
       k=p->adjvex;
       if(!(--indegree[k])) // 若入度減為0,則入棧
         Push(S,k);
     }
   }
   if(count<G.vexnum)
   {
     printf("此有向圖有回路\n");
     return ERROR;
   }
   else
   {
     printf("為一個拓撲序列。\n");
     return OK;
   }
 }

 void main()
 {
   ALGraph f;
   printf("請選擇有向圖\n");
   CreateGraph(f);
   Display(f);
   TopologicalSort(f);
 }