<問題> 図6.9の疑似コードを読み、図6.7についてルートの頂点1から、グラフを幅優先探索するプログラムを実現しなさい。適当にプリントしなさい。

<実行結果例>　
num[1] = 1　（num配列をプリントしています）
num[2] = 2
num[3] = 4
num[4] = 6
num[5] = 3
num[6] = 5
num[7] = 7
　
（上の情報は、下の情報を表しています。完成したプログラムにプリント文を入れるなどして、いろいろな情報を確かめてみてください）
1 th --> v 1　　（1番目に訪問するのは、頂点１というつもり）
2 th --> v 2　　
3 th --> v 5
4 th --> v 3
5 th --> v 6
6 th --> v 4
7 th --> v 7

解答例
#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);

/* 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++) /* num配列は、各頂点（添え字）について、訪問済かどうかを記録。初期値はすべて0。未訪問 */
      num[w] = 0;

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

   while (!empty(Queue)) { /* キューが空でない間 */
      w = dequeue(Queue); /* 先頭の要素の取り出し。スタックならpopup。キューならdequeue。同じこと */
      if (num[w] == 0) { /* 未訪問なら、以下。訪問の場合は、無視 */
           /* printf("%d th --> node %d \n",c, w); */
         num[w] = c; /* 訪問済と、カウンターを記録 */
         c++; /* カウンターをインクリメント */

         for (u = Out[w]->next ; u != NULL; u = u->next) /* 頂点wについて、リストを辿る */
            if (num[u->data] == 0)
               enqueue(Queue, u->data); /* 隣接する頂点で、未訪問の頂点を、キューに追加 */
      }
      printf("QUEUE\n"); /* 美しくないけれども、各回のキューの情報をプリント */
      printlist1(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);
}

STEP 5.5 幅優先探索 (breadth-first search) 問6.2

STEP 5.5　幅優先探索
(breadth-first search)　問6.2