發(fā)布人：suny 發(fā)布時(shí)間：2002-12-26 10:17:45 
----------------------------------------------------------------------- 
 
/* ======================================== */
/*    圖形的深度優(yōu)先搜尋法                  */
/* ======================================== */
#include <stdlib.h>

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[9];              /* 圖形頂點(diǎn)結(jié)構(gòu)數(shù)組   */
int visited[9];                   /* 遍歷記錄數(shù)組       */

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

   for ( i = 0; i < num; i++ )    /* 讀取邊線(xiàn)的回路     */
   {
      from = node[i*2];           /* 邊線(xiàn)的起點(diǎn)         */
      to = node[i*2+1];           /* 邊線(xiàn)的終點(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é)尾           */
   }
}

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

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

/* ---------------------------------------- */
/*  主程式: 建立圖形后,將遍歷內(nèi)容印出.      */
/* ---------------------------------------- */
void main()
{
   graph ptr;
   int node[20][2] = { {1, 2}, {2, 1},  /* 邊線(xiàn)數(shù)組     */
                       {1, 3}, {3, 1},
                       {2, 4}, {4, 2},
                       {2, 5}, {5, 2},
                       {3, 6}, {6, 3},
                       {3, 7}, {7, 3},
                       {4, 8}, {8, 4},
                       {5, 8}, {8, 5},
                       {6, 8}, {8, 6},
                       {7, 8}, {8, 7} };
   int i;

   for ( i = 1; i <= 8; i++ )
   {
      head[i].vertex = i;         /* 設(shè)定頂點(diǎn)值         */
      head[i].nextnode = NULL;    /* 清除圖形指標(biāo)       */
      visited[i] = 0;             /* 設(shè)定遍歷初值       */
   }
   creategraph(node,20);          /* 建立圖形           */
   printf("圖形的鄰接鏈表內(nèi)容:\n");
   for ( i = 1; i <= 8; i++ )
   {
      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");               /* 換行               */
   }
   printf("圖形的深度優(yōu)先遍歷內(nèi)容:\n");
   dfs(1);                        /* 印出遍歷過(guò)程       */
   printf("\n");                  /* 換行               */
}