/* ======================================== */
/*              圖形的遍歷                  */
/* ======================================== */
#include <stdlib.h>
#define MAXQUEUE 70               /* 佇列的最大容量       */

struct node                       /* 圖形頂點(diǎn)結(jié)構(gòu)宣告     */
{
   int vertex;                    /* 頂點(diǎn)資料             */
   struct node *nextnode;         /* 指下一頂點(diǎn)的指標(biāo)     */
};
typedef struct node *graph;       /* 圖形的結(jié)構(gòu)新型態(tài)     */
struct node head[61];              /* 圖形頂點(diǎn)結(jié)構(gòu)數(shù)組     */
int visited[61];                   /* 遍歷記錄數(shù)組         */

int queue[MAXQUEUE];              /* 佇列的數(shù)組宣告       */
int front = -1;                   /* 佇列的前端           */
int rear = -1;                    /* 佇列的后端           */

/* ---------------------------------------- */
/*  建立圖形                                */
/* ---------------------------------------- */
void creategraph(int *node,int num)
{
   graph newnode;                 /* 新頂點(diǎn)指標(biāo)           */
   graph ptr;
   int from;                      /* 邊線的起點(diǎn)           */
   int to;                        /* 邊線的終點(diǎn)           */
   int i;

   for ( i = 0; i < num; i++ )    /* 讀取邊線的回路       */
   {
      from = node[i*2];           /* 邊線的起點(diǎn)           */
      to = node[i*2+1];           /* 邊線的終點(diǎn)           */
      /* 建立新頂點(diǎn)記憶體 */
      newnode = ( graph ) malloc(sizeof(struct node));
      newnode->vertex = to;       /* 建立頂點(diǎn)內(nèi)容         */
      newnode->nextnode = NULL;   /* 設(shè)定指標(biāo)初值         */
      ptr = &(head[from]);        /* 頂點(diǎn)位置             */
      while ( ptr->nextnode != NULL ) /* 遍歷至鏈表尾     */
         ptr = ptr->nextnode;         /* 下一個(gè)頂點(diǎn)       */
      ptr->nextnode = newnode;        /* 插入結(jié)尾         */
   }
}

/* ---------------------------------------- */
/*  佇列資料的存入                          */
/* ---------------------------------------- */
int enqueue(int value)
{
   if ( rear >= MAXQUEUE )        /* 檢查佇列是否全滿     */
      return -1;                  /* 無法存入             */
   rear++;                        /* 后端指標(biāo)往前移       */
   queue[rear] = value;           /* 存入佇列             */
}

/* ---------------------------------------- */
/*  佇列資料的取出                          */
/* ---------------------------------------- */
int dequeue()
{
   if ( front  == rear )          /* 檢查佇列是否是空     */
      return -1;                  /* 無法取出             */
   front++;                       /* 前端指標(biāo)往前移       */
   return queue[front];           /* 佇列取出             */
}

/* ---------------------------------------- */
/*  圖形的廣度優(yōu)先搜尋法                    */
/* ---------------------------------------- */
void bfs(int current)
{
   graph ptr;
0
   /* 處理第一個(gè)頂點(diǎn) */
   enqueue(current);              /* 將頂點(diǎn)存入佇列       */
   visited[current] = 1;          /* 記錄已遍歷過         */
   printf("[%d]     ",current);   /* 印出遍歷頂點(diǎn)值       */
   while ( front != rear )        /* 佇列是否是空的       */
   {
      current = dequeue();        /* 將頂點(diǎn)從佇列取出     */
      ptr = head[current].nextnode;   /* 頂點(diǎn)位置         */
      while ( ptr != NULL )           /* 遍歷至鏈表尾     */
      {
         if ( visited[ptr->vertex] == 0 ) /* 如過沒遍歷過 */
         {
            enqueue(ptr->vertex);     /* 遞回遍歷呼叫     */
            visited[ptr->vertex] = 1; /* 記錄已遍歷過     */
            /* 印出遍歷頂點(diǎn)值 */
     printf("[%d]    ",ptr->vertex);
         }
         ptr = ptr->nextnode;     /* 下一個(gè)頂點(diǎn)           */
      }
   }
}

/* ---------------------------------------- */
/*  圖形的深度優(yōu)先搜尋法                    */
/* ---------------------------------------- */
void dfs(int current)
{
   graph ptr;

   visited[current] = 1;          /* 記錄已遍歷過       */
   printf("[%d]    ",current);   /* 印出遍歷頂點(diǎn)值     */
   ptr = head[current].nextnode;  /* 頂點(diǎn)位置           */
   while ( ptr != NULL )          /* 遍歷至鏈表尾       */
   {
      if ( visited[ptr->vertex] == 0 )  /* 如過沒遍歷過 */
         dfs(ptr->vertex);              /* 遞回遍歷呼叫 */
      ptr = ptr->nextnode;              /* 下一個(gè)頂點(diǎn)   */
   }
}

/* ---------------------------------------- */
/*  主程式: 建立圖形后,將遍歷內(nèi)容印出.      */
/* ---------------------------------------- */
void main()
{clrscr();

while(1)
{
   char c,a;
   graph ptr;
   int i;
   int node[60][2] = { {1,10}, {10, 1},  /* 邊線數(shù)組       */
         {2, 10}, {10, 2},
         {2, 3}, {3, 2},
         {3, 4}, {4, 3},
         {3, 12}, {12, 3},
         {4, 13}, {13, 4},
         {4, 5}, {5, 4},
         {5, 6}, {6, 5},
         {5, 7}, {7, 5},
         {7, 8}, {8, 7},
         {9, 10}, {10, 9},
         {10, 11}, {11, 10},
         {11, 14}, {14, 11},
         {11, 12}, {12, 11},
         {12, 15}, {15, 12},
         {12, 13}, {13, 12},
         {13, 16}, {16, 13},
         {14, 17}, {17, 14},
         {14, 18}, {18, 14},
         {15, 19}, {19, 15},
         {16, 20}, {20, 16},
         {17, 18}, {18, 17},
         {18, 23}, {23, 18},
         {18, 19}, {19, 18},
         {19, 23}, {23, 19},
         {19, 24}, {24, 19},
         {19, 20}, {20, 19},
         {20, 21}, {21, 20},
         {22, 23}, {23, 22},
         {24, 25}, {25,24}
         };
clrscr();
printf("\n\n\n");
printf("/*------------------------------------------------------*/\n");
printf("/*                 歡 迎 使 用 本 程 序                 */\n");
printf("/*------------------------------------------------------*/\n");
printf("      本 程 序 是 有 關(guān) 圖 的 遍 歷 的 算 法 演 示,\n");
printf("如 果 有 不 足 之 處 敬 請(qǐng) 原 諒!\n\n");
printf("請(qǐng) 問 你 是 否 要 運(yùn) 行 以 下 的 程 序:\n\n");
printf("   圖 的 深 度 遍 歷 和 廣 度 遍 歷? Y/N?\n");
c=getch();
if(c!='y'&&'Y')
exit(0);
 clrscr();

printf("\n\n");
printf("請(qǐng) 注 意 以 下 為 各 城 市 的 代 碼:\n\n");

printf("1:烏魯木齊; 2:呼和浩特; 3:北京; 4:天津; 5:沈陽; \n");
printf("6:大連; 7:長(zhǎng)春; 8:哈爾濱; 9:西寧; 10:蘭州;\n");
printf("11:西安; 12:鄭州; 13:徐州; 14:成都; 15:武漢; \n");
printf("16:上海; 17:昆明; 18:貴陽; 19:株州; 20:南昌;\n");
printf("21:福州; 22:南寧; 23:柳州; 24:廣州; 25:深圳.\n");

   for (i=1;i<=25;i++ )
   {
      head[i].vertex=i;         /* 設(shè)定頂點(diǎn)值           */
      head[i].nextnode=NULL;    /* 清除圖形指標(biāo)         */
      visited[i]=0;             /* 設(shè)定遍歷初值         */
   }
   creategraph(node,60);          /* 建立圖形             */
   printf("圖 形 的 鄰 接 鏈 表 內(nèi) 容:\n");
   for (i=1;i<=25;i++)
   {  if(i%3==0)printf("\n");
      printf("頂點(diǎn)%d=>",head[i].vertex); /* 頂點(diǎn)值       */
      ptr=head[i].nextnode;             /* 頂點(diǎn)位置     */
      while(ptr!=NULL)       /* 遍歷至鏈表尾         */
      {
  printf("%d  ",ptr->vertex);  /* 印出頂點(diǎn)內(nèi)容     */
  ptr=ptr->nextnode;         /* 下一個(gè)頂點(diǎn)       */
      }
   }
printf("\n\n");
printf("請(qǐng) 選 擇 你 需 要 的 操 作\n");
printf("1、圖形的廣度優(yōu)先遍歷請(qǐng)輸入:'g'或'G'\n");
printf("2、圖形的深度優(yōu)先遍歷請(qǐng)輸入:'s'或'S'\n");
 c=getch();
  switch(c)
{
  case'g':case'G':
   printf("\n請(qǐng) 你 輸 入 你 需 要 的 起 始 頂 點(diǎn):\n");
   scanf("%d",&i);
   clrscr();
   printf("\n\n");
   printf("請(qǐng) 注 意 以 下 為 各 城 市 的 代 碼:\n\n");
   printf("1:烏魯木齊; 2:呼和浩特; 3:北京; 4:天津; 5:沈陽; \n");
   printf("6:大連; 7:長(zhǎng)春; 8:哈爾濱; 9:西寧; 10:蘭州;\n");
   printf("11:西安; 12:鄭州; 13:徐州; 14:成都; 15:武漢; \n");
   printf("16:上海; 17:昆明; 18:貴陽; 19:株州; 20:南昌;\n");
   printf("21:福州; 22:南寧; 23:柳州; 24:廣州; 25:深圳.\n");

   printf("圖  形  的  廣  度  優(yōu)  先  遍  歷  的  頂  點(diǎn)  內(nèi)  容:\n");
   bfs(i);                        /* 印出遍歷過程         */
   printf("\n");     /*     換行      */
   break;
 case's':case'S':
    printf("\n請(qǐng) 輸 入 你 需 要 的 起 始 頂 點(diǎn):\n");
    scanf("%d",&i);
    clrscr();
   printf("\n\n");
    printf("請(qǐng) 注 意 以 下 為 各 城 市 的 代 碼:\n\n");
    printf("1:烏魯木齊; 2:呼和浩特; 3:北京; 4:天津; 5:沈陽; \n");
    printf("6:大連; 7:長(zhǎng)春; 8:哈爾濱; 9:西寧; 10:蘭州;\n");
    printf("11:西安; 12:鄭州; 13:徐州; 14:成都; 15:武漢; \n");
    printf("16:上海; 17:昆明; 18:貴陽; 19:株州; 20:南昌;\n");
    printf("21:福州; 22:南寧; 23:柳州; 24:廣州; 25:深圳.\n");

    printf("圖  形  的  深  度  優(yōu)  先  遍  歷  的  頂  點(diǎn)  內(nèi)  容:\n");
    dfs(i);                        /* 印出遍歷過程       */
    printf("\n");                  /* 換行               */
     break;
}
printf("\n請(qǐng) 問 你 是 否 要 繼 續(xù):y/n");
a=getch();
if(a!='y'&&'Y')
exit(0);
}
}