//* * * * * * * * * * * * * * * * * * * * * * * *
//*CHAPTER          :5  (5_1)                   *
//*PROGRAM          :圖的遍歷                   *
//*CONTENT          :生成，深度、廣度優先遍歷   *
//* * * * * * * * * * * * * * * * * * * * * * * *
#include <dos.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_VERTEX_NUM 20 //圖的最大頂點數
#define MAXQSIZE 30       //隊列的最大容量 
enum BOOL {False,True};
typedef struct ArcNode
{int adjvex;              //該弧所指向的頂點的位置
 struct ArcNode *nextarc; //指向下一條弧的指針
}ArcNode;       //弧結點
typedef struct
{ArcNode* AdjList[MAX_VERTEX_NUM]; //指向第一條依附該頂點的弧的指針
 int vexnum,arcnum;                //圖的當前頂點和弧數 
 int GraphKind;    //圖的種類，0---無向圖，1---有向圖
}Graph;   
typedef struct        //隊列結構
{int  elem[MAXQSIZE]; //數據域
 int front;           //隊頭指針
 int rear;            //隊尾指針
}SqQueue; 
BOOL visited[MAX_VERTEX_NUM]; //全局變量——訪問標志數組
void CreateGraph(Graph &);    //生成圖的鄰接表
void DFSTraverse(Graph);      //深度優先搜索遍歷圖
void DFS(Graph,int);           
void BFSTraverse(Graph);      //廣度優先搜索遍歷圖
void Initial(SqQueue &);      //初始化一個隊列
BOOL QueueEmpty(SqQueue);     //判斷隊列是否空
BOOL EnQueue(SqQueue &,int);   //將一個元素入隊列
BOOL DeQueue(SqQueue &,int &); //將一個元素出隊列
int  FirstAdjVex(Graph,int);   //求圖中某一頂點的第一個鄰接頂點
int  NextAdjVex(Graph,int,int); //求某一頂點的下一個鄰接頂點
void main()
{Graph G;  //采用鄰接表結構的圖
 char j='y';
 textbackground(3);  //設定屏幕顏色
 textcolor(15);
 clrscr();
 //------------------程序解說----------------------------
 printf("本程序將演示生成一個圖，并對它進行遍歷.\n");
 printf("首先輸入要生成的圖的種類.\n");
 printf("0---無向圖, 1--有向圖\n");
 printf("之后輸入圖的頂點數和弧數。\n格式：頂點數，弧數；例如:4,3\n");
 printf("接著輸入各邊(弧尾，弧頭).\n例如:\n1,2\n1,3\n2,4\n");
 printf("程序會生成一個圖，并對它進行深度和廣度遍歷.\n");
 printf("深度遍歷:1->2->4->3\n廣度遍歷:1->2->3->4\n");
 //------------------------------------------------------
 while(j!='N'&&j!='n')
      {printf("請輸入要生成的圖的種類(0/1):");
       scanf("%d",&G.GraphKind); //輸入圖的種類
       printf("請輸入頂點數和弧數：");
       scanf("%d,%d",&G.vexnum,&G.arcnum); //輸入圖的頂點數和弧數
       CreateGraph(G);       //生成鄰接表結構的圖
       DFSTraverse(G);       //深度優先搜索遍歷圖
       BFSTraverse(G);       //廣度優先搜索遍歷圖
       printf("圖遍歷完畢，繼續進行嗎?(Y/N)");
       scanf(" %c",&j);
     }
}

void CreateGraph(Graph &G)
{//構造鄰接表結構的圖G
 int i;
 int start,end; 
 ArcNode *s;
 for(i=1;i<=G.vexnum;i++) G.AdjList[i]=NULL; //初始化指針數組
 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;
    if(G.GraphKind==0)  //若是無向圖，再插入到終點的弧鏈中
       {s=(ArcNode *)malloc(sizeof(ArcNode));
	s->nextarc=G.AdjList[end];
	s->adjvex=start;
	G.AdjList[end]=s;
       }
   }
}
void DFSTraverse(Graph G)
{//深度優先遍歷圖G
 int i;
 printf("DFSTraverse:");
 for(i=1;i<=G.vexnum;i++) visited[i]=False; //訪問標志數組初始化
 for(i=1;i<=G.vexnum;i++)
     if(!visited[i]) DFS(G,i); //對尚未訪問的頂點調用DFS
 printf("\b\b  \n");
}
void DFS(Graph G,int i)
{//從第i個頂點出發遞歸地深度遍歷圖G
 int w;
 visited[i]=True;  //訪問第i個頂點
 printf("%d->",i);
 for(w=FirstAdjVex(G,i);w;w=NextAdjVex(G,i,w))
   if(!visited[w]) DFS(G,w); //對尚未訪問的鄰接頂點w調用DFS
}

void BFSTraverse(Graph G)
{//按廣度優先非遞歸的遍歷圖G，使用輔助隊列Q和訪問標志數組visited
 int i,u,w;
 SqQueue Q; 
 printf("BFSTreverse:");
 for(i=1;i<=  G.vexnum;i++)  visited[i]=False; //訪問標志數組初始化
 Initial(Q);  //初始化隊列
 for(i=1;i<=G.vexnum;i++)
   if(!visited[i])
     {visited[i]=True;  //訪問頂點i
      printf("%d->",i);
      EnQueue(Q,i);     //將序號i入隊列
      while(!QueueEmpty(Q)) //若隊列不空，繼續
       {DeQueue(Q,u);   //將隊頭元素出隊列并置為u
	for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w))
	  if(!visited[w])  //對u的尚未訪問的鄰接頂點w進行訪問并入隊列
	     {visited[w]=True;
	      printf("%d->",w);
	      EnQueue(Q,w);
	     }
       }
     }
 printf("\b\b  \n");
}

int FirstAdjVex(Graph G,int v)
{//在圖G中尋找第v個頂點的第一個鄰接頂點
 if(!G.AdjList[v]) return 0;
 else return(G.AdjList[v]->adjvex);
}
int NextAdjVex(Graph G,int v,int u)
{//在圖G中尋找第v個頂點的相對于u的下一個鄰接頂點
 ArcNode *p;
 p=G.AdjList[v];
 while(p->adjvex!=u) p=p->nextarc; //在頂點v的弧鏈中找到頂點u
 if(p->nextarc==NULL) return 0;    //若已是最后一個頂點，返回0
 else return(p->nextarc->adjvex);  //返回下一個鄰接頂點的序號
}

void Initial(SqQueue &Q)      
{//隊列初始化
 Q.front=Q.rear=0; 
}
BOOL QueueEmpty(SqQueue Q)
{//判斷隊列是否已空，若空返回True,否則返回False
 if(Q.front==Q.rear) return True;
 else return False;
}

BOOL EnQueue(SqQueue &Q,int ch)
{//入隊列，成功返回True，失敗返回False
 if((Q.rear+1)%MAXQSIZE==Q.front) return False;
 Q.elem[Q.rear]=ch;
 Q.rear=(Q.rear+1)%MAXQSIZE;
 return True;
}

BOOL DeQueue(SqQueue &Q,int &ch)
{//出隊列,成功返回True，并用ch返回該元素值，失敗返回False
 if(Q.front==Q.rear) return False;
 ch=Q.elem[Q.front];
 Q.front=(Q.front+1)%MAXQSIZE;
 return True;                     //成功出隊列，返回True
}