<問題> 図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); }