#include <stdio.h>
#include <stdlib.h>
#define MAX_NAME 3 /* 頂點字符串的最大長度+1 */
#define MAX_INFO 80 /* 相關信息字符串的最大長度+1 */
#define MAX_VERTEX_NUM 20
#define NULL 0
/* 單鏈隊列－－隊列的鏈式存儲結構 */
 typedef struct QNode
 {
   int data;
   struct QNode *next;
 }QNode,*QueuePtr;
 typedef struct
 {
   QueuePtr front,rear; /* 隊頭、隊尾指針 */
 }LinkQueue;
 typedef char InfoType;
 typedef char VertexType[MAX_NAME]; /* 字符串類型 */
/* c7-4.h 無向圖的鄰接多重表存儲表示 */
 typedef enum{unvisited,visited}VisitIf;
 typedef struct EBox
 {
   VisitIf mark; /* 訪問標記 */
   int ivex,jvex; /* 該邊依附的兩個頂點的位置 */
   struct EBox *ilink,*jlink; /* 分別指向依附這兩個頂點的下一條邊 */
   InfoType *info; /* 該邊信息指針 */
 }EBox;
 typedef struct
 {
   VertexType data;
   EBox *firstedge; /* 指向第一條依附該頂點的邊 */
 }VexBox;
 typedef struct
 {
   VexBox adjmulist[MAX_VERTEX_NUM];
   int vexnum,edgenum; /* 無向圖的當前頂點數和邊數 */
 }AMLGraph;
 /* 鏈隊列的基本操作 */
 InitQueue(LinkQueue *Q)
 { /* 構造一個空隊列Q */
   (*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode));
   if(!(*Q).front)
     exit(0);
   (*Q).front->next=NULL;
   return 1;
 }
 QueueEmpty(LinkQueue Q)
 { /* 若Q為空隊列,則返回TRUE,否則返回FALSE */
   if(Q.front==Q.rear)
     return 1;
   else
     return -1;
 }
 EnQueue(LinkQueue *Q,int e)
 { /* 插入元素e為Q的新的隊尾元素 */
   QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
   if(!p) /* 存儲分配失敗 */
     exit(0);
   p->data=e;
   p->next=NULL;
   (*Q).rear->next=p;
   (*Q).rear=p;
   return 1;
 }
 DeQueue(LinkQueue *Q,int *e)
 { /* 若隊列不空,刪除Q的隊頭元素,用e返回其值,并返回OK,否則返回ERROR */
   QueuePtr p;
   if((*Q).front==(*Q).rear)
     return -1;
   p=(*Q).front->next;
   *e=p->data;
   (*Q).front->next=p->next;
   if((*Q).rear==p)
     (*Q).rear=(*Q).front;
   free(p);
   return 1;
 }
 /* 無向圖的鄰接多重表存儲 */
 int LocateVex(AMLGraph G,VertexType u)
 { /* 初始條件: 無向圖G存在,u和G中頂點有相同特征 */
   /* 操作結果: 若G中存在頂點u,則返回該頂點在無向圖中位置;否則返回-1 */
   int i;
   for(i=0;i<G.vexnum;++i)
     if(strcmp(u,G.adjmulist[i].data)==0)
       return i;
   return -1;
 }
AMLGraph * CreateGraph(AMLGraph *G)
 { /* 采用鄰接多重表存儲結構,構造無向圖G */
   int i,j,k,l,IncInfo;
   char s[MAX_INFO];
   VertexType va,vb;
   EBox *p;
   printf("請輸入無向圖G的頂點數,邊數: ");
   scanf("%d,%d",&(*G).vexnum,&(*G).edgenum);
   printf("請輸入%d個頂點的值(<%d個字符):\n",(*G).vexnum,MAX_NAME);
   for(i=0;i<(*G).vexnum;++i) /* 構造頂點向量 */
   {
     scanf("%s",(*G).adjmulist[i].data);
     (*G).adjmulist[i].firstedge=NULL;
   }
   printf("請順序輸入每條邊的兩個端點(以空格作為間隔):\n");
   for(k=0;k<(*G).edgenum;++k) /* 構造表結點鏈表 */
   {
     scanf("%s%s",va,vb); /* 讀入兩個頂點*/
     i=LocateVex(*G,va); /* 一端 */
     j=LocateVex(*G,vb); /* 另一端 */
     p=(EBox*)malloc(sizeof(EBox));
     p->mark=unvisited; /* 設初值 */
     p->ivex=i;
     p->jvex=j;
     p->info=NULL;
     p->ilink=(*G).adjmulist[i].firstedge; /* 插在表頭 */
     (*G).adjmulist[i].firstedge=p;
     p->jlink=(*G).adjmulist[j].firstedge; /* 插在表頭 */
     (*G).adjmulist[j].firstedge=p;
   }
   return   G;
 }
 VertexType* GetVex(AMLGraph G,int v)
 { /* 初始條件: 無向圖G存在,v是G中某個頂點的序號。操作結果: 返回v的值 */
   if(v>=G.vexnum||v<0)
     exit(0);
   return &G.adjmulist[v].data;
 }
int  visite[MAX_VERTEX_NUM]; /* 訪問標志數組(全局量) */
 int (*VisitFunc)(VertexType v);
 void DFS(AMLGraph G,int v)
 {
   int j;
   EBox *p;
   VisitFunc(G.adjmulist[v].data);
   visite[v]=1;
   p=G.adjmulist[v].firstedge;
   while(p)
   {
     j=p->ivex==v?p->jvex:p->ivex;
     if(!visite[j])
       DFS(G,j);
     p=p->ivex==v?p->ilink:p->jlink;
   }
 }
 void DFSTraverse(AMLGraph G,int(*visit)(VertexType))
 { /* 初始條件: 圖G存在,Visit是頂點的應用函數。算法7.4 */
   /* 操作結果: 從第1個頂點起,深度優先遍歷圖G,并對每個頂點調用函數Visit */
   /*           一次且僅一次。一旦Visit()失敗,則操作失敗 */
   int v;
   VisitFunc=visit;
   for(v=0;v<G.vexnum;v++)
     visite[v]=0; 

   for(v=0;v<G.vexnum;v++)
     if(!visite[v])
       DFS(G,v);
   printf("\n");
 }
 typedef int QElemType; /* 隊列類型 */
 /* BFSTraverse()用 */
 /* BFSTraverse()用 */
 void BFSTraverse(AMLGraph G,int(*Visit)(VertexType))
 { /* 初始條件: 圖G存在,Visit是頂點的應用函數。算法7.6 */
   /* 操作結果: 從第1個頂點起,按廣度優先非遞歸遍歷圖G,并對每個頂點調用函數 */
   /*           Visit一次且僅一次。一旦Visit()失敗,則操作失敗。 */
   /*           使用輔助隊列Q和訪問標志數組visite */
   int v,u,w;
   VertexType w1,u1;
   LinkQueue Q;
   for(v=0;v<G.vexnum;v++)
     visite[v]=0; /* 置初值 */
   InitQueue(&Q); /* 置空的輔助隊列Q */
   for(v=0;v<G.vexnum;v++)
     if(!visite[v]) /* v尚未訪問 */
     {
       visite[v]=1; /* 設置訪問標志為TRUE(已訪問) */
       Visit(G.adjmulist[v].data);
       EnQueue(&Q,v); /* v入隊列 */
       while(!QueueEmpty(Q)) /* 隊列不空 */
       {
         DeQueue(&Q,&u); /* 隊頭元素出隊并置為u */
         strcpy(u1,*GetVex(G,u));
         for(w=FirstAdjVex(G,u1);w>=0;w=NextAdjVex(G,u1,strcpy(w1,*GetVex(G,w))))
           if(!visite[w]) /* w為u的尚未訪問的鄰接頂點的序號 */
           {
      visite[w]=1;
             Visit(G.adjmulist[w].data);
             EnQueue(&Q,w);
           }
       }
     }
   printf("\n");
 }
 void MarkUnvizited(AMLGraph G)
 { /* 置邊的訪問標記為未被訪問 */
   int i;
   EBox *p;
   for(i=0;i<G.vexnum;i++)
   {
     p=G.adjmulist[i].firstedge;
     while(p)
     {
       p->mark=unvisited;
       if(p->ivex==i)
         p=p->ilink;
       else
         p=p->jlink;
     }
   }
 }
 void Display(AMLGraph G)
 { /* 輸出無向圖的鄰接多重表G */
   int i;
   EBox *p;
   MarkUnvizited(G); /* 置邊的訪問標記為未被訪問 */
   printf("%d個頂點：\n",G.vexnum);
   for(i=0;i<G.vexnum;++i)
     printf("%s ",G.adjmulist[i].data);
   printf("\n%d條邊:\n",G.edgenum);
   for(i=0;i<G.vexnum;i++)
   {
     p=G.adjmulist[i].firstedge;
     while(p)
       if(p->ivex==i) /* 邊的i端與該頂點有關 */
       {
         if(!p->mark) /* 只輸出一次 */
         {
           printf("%s－%s ",G.adjmulist[i].data,G.adjmulist[p->jvex].data);
           p->mark=visited;
           if(p->info) /* 輸出附帶信息 */
             printf("相關信息: %s ",p->info);
         }
         p=p->ilink;
       }
       else /* 邊的j端與該頂點有關 */
       {
         if(!p->mark) /* 只輸出一次 */
         {
           printf("%s－%s ",G.adjmulist[p->ivex].data,G.adjmulist[i].data);
           p->mark=visited;
           if(p->info) /* 輸出附帶信息 */
             printf("相關信息: %s ",p->info);
         }
         p=p->jlink;
       }
     printf("\n");
   }
 }
/*主程序*/
   visit(VertexType v)
 {
   printf("%s ",v);
   return 1;
 }
 void main()
 {
   int k,n;
   AMLGraph g;
   VertexType v1,v2;
   CreateGraph(&g);
   Display(g);
   printf("DFS:\n");/*深度優先搜索的結果*/
   DFSTraverse(g,visit);
   printf("BFS:\n");/*廣度優先搜索的結果*/
   BFSTraverse(g,visit);
   DestroyGraph(&g);
 }