課題１ | 応用アルゴリズム演習

今回は、演習時間も短いし、プログラミングなしの課題となっています。

有向グラフを深さ優先探索してみましょう。プログラムはこちらにあるので、プログラムの実行理解をしましょう。ついでに、デバッガでプログラムがどのように動作しているか、しっかり追っかけられるようになりましょう。

まずは、データ構造。 id はノードの識別子であり， visited はノードの訪問回数を示す。 struct node はグラフのノードを表し、配列 neighbors がノードへの参照を値として持つことは、そのノードから参照先ノードへのエッジ（edge）が存在することを示している。当ノードが持つエッジの数は neighborsCount で記録しております。neighbors の配列の中に、i < neighborsCount でしたら、neighbors[i] が意味があります。

#define BUFSIZE 100
#define MAX_NEIGHBORS 10

typedef struct node {
    int id; /* ノード名*/
    int visited; /* 探索された回数 */
    int neighborCount; /* 隣接するノードの数、neighbors 配列の最大引数 */
    struct node * neighbors[MAX_NEIGHBORS]; /* 隣接するノードの配列、ポインターとして記録 */
} node_t;

node_t nodes[BUFSIZE];

一方で、探索プログラムはこんな感じ。再帰的に探索をおこなうが、１度たどったところは、２度以上探索しないようにしています。エッジは、neighbors 配列の順で調べていきます。

/* 深さ優先探索 */
void dfs(node_t * node) {
    printNode(node);
    node->visited++;
    if (node->visited == 1) { /* 当 node が初めて出た場合は… */
        int n;
        for (n = 0; n < node->neighborCount; n++) { /* …隣接するノードを再帰的に探索 */
            node_t * next = node->neighbors[n];
            dfs(next);
        }
    }
    /* 初めてじゃ無かった時、あるいは隣接するノード全部探索済みになった時に、呼出側に戻る */
}

下記が、グラフを作成してから探索を行っている部分。

/* n ノードを初期化する */
void initNodes(int n) {
    int i;
    for(i = 0; i<n; i++) {
        nodes[i].id = i;
        nodes[i].visited = 0;
        nodes[i].neighborCount = 0;
    }
}

/* origin から destination へ枝を追加 */
void link(node_t * origin, node_t * destination) {
    origin->neighbors[origin->neighborCount] = destination;
    origin->neighborCount++;
}

void test1(void) {
    /* グラフの定義 */
    initNodes(4);
    link(&nodes[0], &nodes[2]); /* 0 -> 2 */
    link(&nodes[0], &nodes[1]); /* 0 -> 1 */

    link(&nodes[1], &nodes[2]); /* 1 -> 2 */
    link(&nodes[1], &nodes[3]); /* 1 -> 3 */
    
    link(&nodes[2], &nodes[3]); /* 2 -> 3 */
    
    link(&nodes[3], &nodes[0]); /* 3 -> 0 */

    /* 深さ優先探索 */
    dfs(&nodes[0]); /* ノード 0 からスタート */
}

例えば、test1() の場合、以下のようなグラフができているはず。あるノードから枝が２つある場合は、s の枝が先に探索されます。

さて、以下が課題になります。

問題１

test1() を実行した際の実行結果を確認しましょう。

int main(void)  {
    test1();
    return 0;
}

その上で、関数の Call Stack がどのように変化しながらプログラム実行が進んでいたか、コメント風に記述しなさい。冒頭部だけ書くと、こんな感じ。

(node 0, visited 0 times) // stack:0
(node 2, visited 0 times) // stack:0:2
(node 3, visited 0 times) // ...
(node 0, visited 1 times) // 
(node 1, visited 0 times) // 
(node 2, visited 1 times) //
(node 3, visited 1 times) //

// stack:.. の部分は、頭で考えてもらっても良いし、デバッガでprintNodes()に break point をいれて、調べても良いし、以下の option 課題を解くことで実現しても良いです。

問題２

dfs 関数中の if 文を以下のように書き換えたとします。

void dfs(node_t * node) {
    printNode(node);
    node->visited++;
    if (1) { /* 変更点！ 常に then 節を実行 */
        int n;
        for (n = 0; n < node->neighborCount; n++) {
            node_t * next = node->neighbors[n];
            dfs(next);
        }
    }
}

つまり、同じノードを何度でも探索しなおすこととします。

質問１ このとき test2 を実行した際の nodes[10] の訪問回数は、どうなるでしょう？ nodes[12] の訪問回数？ nodes[5] の訪問回数は？
質問２ このとき test2 を実行した時、なぜ無限ループになりませんでしたか？

void test2(void) {
    int i;
    initNodes(13); /* ノード 0 を使わない、ノード 1～12 を準備 */
    for(i=3; i<13; i++) {
        link(&nodes[i], &nodes[i-1]); /* i -> i-1 */
        link(&nodes[i], &nodes[i-2]); /* i -> i-2 */
    }
    
    /* 深さ優先探索 */
    dfs(&nodes[10]); /* ノード 10 からスタート */
}

真面目に手でやると大変なんですが、実は、nodes[10] の訪問回数は fib(10) に一致します。理由を考え、簡単に答えましょう。ちなみに、fib(n) はフィボナッチ関数のことで、

int fib(int n) {
    if(n==0 || n==1) {
        return 1;
    }
    return fib(n-1)+fib(n-2);
}

で求まる関数とします。

問題３（オプション課題）

上記の問題１の深さ優先探索は再帰関数で実装されました。自作のスタックを（ある程度汎用的に）作って、再帰でない実装に変化してみて下さい。

オプション課題なので、全員がとかなくても大丈夫です。ただ、次の課題にいい練習になります。スタックの実装だけを提出、アルゴリズムの実装も提出しても構いません。 上手く行けなくても評価するので、是非やってみて、出来たものを提出してください。

提出に求めるのが：

ソースコード
レポート（データ構造の説明、再帰実装の違うところ、最大半ページ程度）

課題提出

レポートを PDF で作成し、Beef＋　から提出してください。

オプション課題を解いた人は、プログラムも提出すること。 提出締め切りは、10/19(木) 12:00

再提出

問題１の再提出を認めます．

この資料をご覧になって更新したkadai1.c の test3() で作成されているグラフでもう一度取り組んでみて下さい．提出はBeef＋の課題１＝再提出＝，締め切りは11/24（金）