STEP 5.5　幅優先探索 ー リスト操作関数の利用

• 上の文字列str中、２番目の動物を表示する。

解答例
#include "list.h"

#define N 7

List *Out[N+1]; /* 図6.7を、V1からV7と考える */
int num[N+1];

void BFS(int);
void printlist1 (List *L);

/* 追加 リスト関係の関数テンプレート */
char head(List *L);
List *tail(List *L);
void printlist2 (List *L);

/* 先頭の要素を取り出す関数 */
char head(List *L) {
   access(L, 1);
}

/* 先頭の要素を除く残りのリストを返す関数 */
List *tail(List *L) {
   return (L -> next);
}

/* 下のprintList1を、書き直し */
/* リスト操作関数で出力  再帰で書いた */
void printlist2 (List *L) {
   if (!empty(L)) {
      printf("%d \n", head(L));  /* dataはchar。charのサイズの正のintとして見る */
      printlist2(tail(L));
  }
}

/* 以前の関数 List構造体のdataメンバーを、intとして出力するための関数 */
/* 直接構造体の中を辿る */
void printlist1 (List *L) {
   while (L != NULL) {
     if (L -> data != '\0')
        printf("%d \n", L -> data);
     L = L -> next;
   }
}

/* BFSを作成 解答例 */
void BFS(int v) {
   int w, c;
   List *Queue; /* 探索管理はキュー */
   List *u; /* 各頂点ごとの隣接リストを扱うための変数 */

   c = 1; /* cは、訪問順カウンター */

   for (w = 1; w < N+1; w++) /*  closed リストの初期化 */
      num[w] = 0;

   Queue = create(); /* initialize のこと。ヘッダーにNULLをセット */
   enqueue(Queue, v); /* スタートの頂点を、エンキュー */

   while (!empty(Queue)) { /* キューが空でない間 */
      w = dequeue(Queue); /* 先頭の要素の取り出し */
      if (num[w] == 0) { /* 未訪問の頂点なら、進む*/
           /* printf("%d th --> node %d \n",c, w); */
         num[w] = c; /*  closed リストの処理 */
         c++; /*  訪問順カウンターのインクリメント */

         for (u = Out[w] ; !empty(u);  u = tail(u)) /* 頂点wについて、uでリストをたどる。このforループを再帰関数にする方法もあるだろう */
            if (num[head(u)] == 0) /* 未訪問の頂点だったら */
               enqueue(Queue, head(u)); /* キューに追加 */
      }
      printf("QUEUE\n"); /* 各回のキューの情報をプリント */
  /*    printlist1(Queue); */
      printlist2(Queue);
   }

   FreeData(Queue); FreeData(u);
}


int main(void){
   int i;

   /* 隣接リストを、リスト構造に (STEP5.2) */
   for(i=1;i<N+1;i++){
      Out[i]=create();
   }

   insert(Out[1],1,2); insert(Out[1],2,5);
   insert(Out[2],1,3); insert(Out[2],2,5); insert(Out[2],3,6);
   insert(Out[3],1,6);
   insert(Out[4],1,1); insert(Out[4],2,5);
   insert(Out[5],1,4); insert(Out[5],2,6);
   insert(Out[6],1,3); insert(Out[6],2,7);
   insert(Out[7],1,5); insert(Out[7],2,6);

   BFS(1);
   for (i=1; i < N+1; i++) /* num配列をプリント。各頂点が何番目に訪問されたかをプリント */
      printf("num[%d] = %3d \n", i, num[i]);

   return(0);
}