//* * * * * * * * * * * * * * * * * * * * * * * *
//*CHAPTER          :5  (5_3)                   *
//*PROGRAM          :拓撲排序      	        *
//*CONTENT          :拓撲排序                   *
//* * * * * * * * * * * * * * * * * * * * * * * *
#include <dos.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_VERTEX_NUM 20 //圖的最大頂點數
#define MAX 30       //棧的最大容量
enum BOOL {False,True};
typedef struct ArcNode
{int adjvex;              //該弧所指向的頂點的位置
 struct ArcNode *nextarc; //指向下一條弧的指針
}ArcNode;       //弧結點
typedef struct
{int indegree[MAX_VERTEX_NUM]; //存放各頂點的入度
 ArcNode* AdjList[MAX_VERTEX_NUM]; //指向第一條依附該頂點的弧的指針
 int vexnum,arcnum;                //圖的當前頂點和弧數
}Graph;
typedef struct    //定義堆棧結構
{int elem[MAX];   //棧區
 int top;         //棧頂指針
}Stack;
void CreateGraph(Graph &);    //生成圖的鄰接表
BOOL TopologicalSort(Graph);  //進行拓撲排序
void FindInDegree(Graph&);    //求圖各頂點的入度
void Initial(Stack &);     //初始化一個堆棧
BOOL Push(Stack &,int); //將一個元素入棧
BOOL Pop(Stack&,int &); //將一個元素出棧
BOOL StackEmpty(Stack); //判斷堆棧是否為空
void main()
{Graph G;  //采用鄰接表結構的圖
 char j='y';
 BOOL temp;
 textbackground(3);  //設定屏幕顏色
 textcolor(15);
 clrscr();
 //------------------程序解說----------------------------
 printf("本程序將演示怎樣對圖進行拓撲排序.\n");
 printf("首先輸入圖的頂點數和弧數.\n格式：頂點數，弧數；例如:4,4\n");
 printf("再輸入各條弧(弧尾,弧頭).\n例如:\n1,2\n1,3\n2,4\n4,3\n");
 printf("程序將會生成一個圖并對它進行拓撲排序.\n");
 printf("拓撲排序結果:1->2->4->3\n");
 //------------------------------------------------------
 while(j!='N'&&j!='n')
      {CreateGraph(G);          //生成鄰接表結構的圖
       temp=TopologicalSort(G); //進行拓撲排序
       if(temp==False) printf("該圖有回路!\n");
		 //若返回為False,表明該圖存在有環路
       else printf("該圖沒有回路!\n");
       printf("拓撲排序完畢，繼續進行嗎?(Y/N)");
       scanf(" %c",&j);
     }
}

void CreateGraph(Graph &G)
{//構造鄰接表結構的圖G
 int i;
 int start,end;
 ArcNode *s;
 printf("請輸入圖的頂點數和弧數:");
 scanf("%d,%d",&G.vexnum,&G.arcnum); //輸入圖的頂點數和弧數
 for(i=1;i<=G.vexnum;i++) G.AdjList[i]=NULL; //初始化指針數組
 printf("請輸入各弧, 格式：弧尾,弧頭\n");
 for(i=1;i<=G.arcnum;i++)
   {scanf("%d,%d",&start,&end); //輸入弧的起點和終點
    s=(ArcNode *)malloc(sizeof(ArcNode)); //生成一個弧結點
    s->nextarc=G.AdjList[start]; //插入到鄰接表中
    s->adjvex=end;
    G.AdjList[start]=s;
   }
}
BOOL TopologicalSort(Graph G)
{//對圖G進行拓撲排序，若G存在回路，返回False,否則返回True
 int i,k;
 int count; //計數器
 ArcNode* p;
 Stack S;
 FindInDegree(G); //求出圖中各頂點的入度
 Initial(S);      //堆棧初始化，存放入度為零的頂點
 for(i=1;i<=G.vexnum;i++)
  if(!G.indegree[i]) Push(S,i); //入度為零的頂點入棧
 count=0;     //對輸出頂點記數
 printf("拓撲排序:");
 while(!StackEmpty(S))
  {Pop(S,i);  //輸出i號頂點并記數
   printf("%d->",i);
   count++;
   for(p=G.AdjList[i];p;p=p->nextarc)
     {k=p->adjvex;       //對i號頂點的每個鄰接頂點的入度減一
      if(!(--G.indegree[k])) Push(S,k); //若入度為零，入棧
     }
  }
 printf("\b\b  \n");
 if(count<G.vexnum) return False; //如輸出頂點數少于圖中頂點數，則該圖有回路
 else return True;
}
void FindInDegree(Graph &G)
{//求出圖G的各頂點的入度，存放在G.indegree[1..G.vexnum]中
 int i;
 ArcNode* p;
 for(i=1;i<=G.vexnum;i++)
   G.indegree[i]=0; 
 for(i=1;i<=G.vexnum;i++)
    {
     for(p=G.AdjList[i];p;p=p->nextarc)
       G.indegree[p->adjvex]++;  //弧頭頂點的入度加一
    }
}
void Initial(Stack &S)
{S.top=-1;   //棧頂指針初始化為-1
}

BOOL Push(Stack &S,int ch)
{//將元素ch入棧，成功返回True,失敗返回False
 if(S.top>=MAX-1) return False;//判斷是否棧滿
 else {S.top++;               //棧頂指針top加一
       S.elem[S.top]=ch;      //入棧
       return True;
      }
}

BOOL Pop(Stack &S,int &ch)
{//將棧頂元素出棧,成功返回True，并用ch返回該元素值，失敗返回False
 if(S.top<=-1) return False;//判斷是否?？? else {S.top--;                                //棧頂指針減一
       ch=S.elem[S.top+1];
       return True;
      }
}
BOOL StackEmpty(Stack S)
{//判斷堆棧是否已空，若空返回True,不空返回False
 if(S.top<=-1) return True;
 else return False;
}