<問題> 図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の疑似コードには、訪問情報を管理する部分がある。

解答例
#include "list.h"

#define N 7

/* 以下、2つの変数は大域変数 全ての関数がアクセス */
List *Out[N+1]; /* 図6.7を、V1からV7と考える */
int num[N+1];   /* 各頂点(添え字)について、値は訪問順位 その頂点を訪問したかどうかの情報 */

void DFS(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;
    }
}

void DFS(int v) {
    int w, c; /* wは、注目している頂点 */
    List *Stack; /* 探索管理用スタック */
    List *u; /* 各頂点について、OUTリスト */

    c = 1; /* 何番目に訪問したか */

    for (w = 1; w < N+1; w++) /* 訪問済リストを全て0に。この配列は訪問順位の数で書き換えられる */
        num[w] = 0;

    Stack = create(); /* initilize(S)にあたる 空スタックの準備 */
    pushdown (Stack, v); /* スタックの操作 STEP5.3 スタートの頂点をプッシュ */

    while (!empty(Stack)) { /* 探索スタックが空でない間 */
        w = popup(Stack); /* 先頭の要素。スタックなので、popup */

        if (num[w] == 0) { /* そこには、まだ行っていない。既に訪問した頂点がポップされた場合は、無視 */
            /*  printf("%d th --> v %d \n",c, w); */
            num[w] = c; /* 頂点wについて、num配列に訪問済を記録。cは訪問順の数 */
            c++; /* カウンターをインクリメント */

            for (u = Out[w]->next ; u != NULL; u = u->next) /* 頂点wの辺について、Out[w]から辿る */
                if (num[u->data] == 0) /* num配列の確認。まだ行っていないところだけ、探索スタックに追加。行っていたら無視 */
                    pushdown(Stack, u->data); /* スタックに積んでいく。pushdown */
        }

        printf("STACK:\n"); /* 美しくないプリントですが、各回のスタックの状態をプリントします */
        printlist1(Stack);
    }

    FreeData(Stack); FreeData(u);
}

int main(void){
    int i;

    /* 隣接リストを、リスト構造に (STEP5.2) */
    for (i=1;i<N+1;i++){
        Out[i]=create(); /* Out配列の各要素は、各頂点のOUTリストへのポインター */
    }

    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);

    DFS(1); 
    for (i=1; i < N+1; i++) /* num配列をプリントして、探索順を確認 */
        printf("num[%d] = %3d \n", i, num[i]);

    return(0);
}

STEP 5.4 深さ優先探索 (depth-first search) 問6.1

STEP 5.4　深さ優先探索
(depth-first search)　問6.1