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

void CreateGraph(Graph &G)
{//構(gòu)造鄰接表結(jié)構(gòu)的圖G
 int i;
 int start,end;
 ArcNode *s;
 printf("請(qǐng)輸入圖的頂點(diǎn)數(shù)和弧數(shù):");
 scanf("%d,%d",&G.vexnum,&G.arcnum); //輸入圖的頂點(diǎn)數(shù)和弧數(shù)
 for(i=1;i<=G.vexnum;i++) G.AdjList[i]=NULL; //初始化指針數(shù)組
 printf("請(qǐng)輸入各弧, 格式：弧尾,弧頭\n");
 for(i=1;i<=G.arcnum;i++)
   {scanf("%d,%d",&start,&end); //輸入弧的起點(diǎn)和終點(diǎn)
    s=(ArcNode *)malloc(sizeof(ArcNode)); //生成一個(gè)弧結(jié)點(diǎn)
    s->nextarc=G.AdjList[start]; //插入到鄰接表中
    s->adjvex=end;
    G.AdjList[start]=s;
   }
}
BOOL TopologicalSort(Graph G)
{//對(duì)圖G進(jìn)行拓?fù)渑判颍鬐存在回路，返回False,否則返回True
 int i,k;
 int count; //計(jì)數(shù)器
 ArcNode* p;
 Stack S;
 FindInDegree(G); //求出圖中各頂點(diǎn)的入度
 Initial(S);      //堆棧初始化，存放入度為零的頂點(diǎn)
 for(i=1;i<=G.vexnum;i++)
  if(!G.indegree[i]) Push(S,i); //入度為零的頂點(diǎn)入棧
 count=0;     //對(duì)輸出頂點(diǎn)記數(shù)
 printf("拓?fù)渑判?");
 while(!StackEmpty(S))
  {Pop(S,i);  //輸出i號(hào)頂點(diǎn)并記數(shù)
   printf("%d->",i);
   count++;
   for(p=G.AdjList[i];p;p=p->nextarc)
     {k=p->adjvex;       //對(duì)i號(hào)頂點(diǎn)的每個(gè)鄰接頂點(diǎn)的入度減一
      if(!(--G.indegree[k])) Push(S,k); //若入度為零，入棧
     }
  }
 printf("\b\b  \n");
 if(count<G.vexnum) return False; //如輸出頂點(diǎn)數(shù)少于圖中頂點(diǎn)數(shù)，則該圖有回路
 else return True;
}
void FindInDegree(Graph &G)
{//求出圖G的各頂點(diǎn)的入度，存放在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]++;  //弧頭頂點(diǎn)的入度加一
    }
}
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;
}