(Visual Studioを使って、分割コンパイルする場合は、STEP5.3の3つのファイルと、下のファイルを１つのプロジェクトにして、プログラムを作ろう)
まず、確認のこと
<問題> 図6.6の疑似コードを読み、図6.7についてルートの頂点1から、グラフを深さ優先探索するプログラムを実現しなさい。適当にプリントしなさい。
<実行結果例>
num[1] = 1 （最終的なNum配列の値を表示します）
num[2] = 7
num[3] = 5
num[4] = 6
num[5] = 2
num[6] = 3
num[7] = 4
（なお、上の情報を書き直すと、以下のような情報です。プログラム中に適切なprint文を入れると出力できます）
1 th --> v 1 （1番目に訪問するのは、頂点１というつもり）
2 th --> v 5
3 th --> v 6
4 th --> v 7
5 th --> v 3
6 th --> v 4
7 th --> v 2
<ヒント> 一度訪問した頂点は、探索しない。図6.6の疑似コードには、訪問情報を管理する部分があるはず。
gcc -c 0504.c
gcc -o dfs 0504.o list.o stackqueue.o (リンクしよう。dfsにしよう！)
<注意> pp. 195 - 198の回答プログラム例について
<0504.cのみ。下のプログラムに適切に追加しなさい>
解答例
#include "list.h"
#define N 7
/* 大域変数 */
List *Out[N+1]; /* 図6.7を、V1からV7と考える */
int num[N+1]; /* この配列は、何を表現しているのだろうか */
void DFS(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;
}
}
void DFS(int v) {
int w, c; /* wとcは、それぞれ何を表しているのだろう */
List *Stack;
List *u;
u = NULL; /* Visual Studioのコンパイラは、ポインターチェックが厳しい。初期化しておきます */
c = 1; /* 1に初期化される。説明できるだろうか */
for (w = 1; w < N+1; w++) /* num配列は、何を表現しているだろう */
num[w] = 0;
Stack = create(); /* initilize(S)にあたる */
pushdown (Stack, v); /* スタックの操作 STEP5.3 */
/* 以下、作成しなさい */
while (!empty(Stack)) {
}
FreeData(Stack); 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);
printf("dfs(1) \n");
DFS(1);
for (i=1; i < N+1; i++)
printf("num[%d] = %3d \n", i, num[i]);
return(0);
}