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

<問題> 図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番目に訪問するのは、頂点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として出力するための関数 */
/* 0502.cからコピー */
void printlist1 (List *L) {
    while (L != NULL) {
       if (L -> data != '\0')
           printf("%d \n", L -> data);
        L = L -> next;
    }
}

/* BFSを作成 */


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); 
    /* num配列は最初全て0。訪問順が代入される */
    for (i=1; i < N+1; i++)
        printf("num[%d] = %3d \n", i, num[i]);

    return(0);
}