課題1
課題1
今回は、演習時間も短いし、プログラミングなしの課題となっています。
有向グラフを深さ優先探索してみましょう。 プログラムはこちら(srcのみ)にあるので、プログラムの実行理解をしましょう。 ついでに、デバッガでプログラムがどのように動作しているか、しっかり追っかけられるようになりましょう。
まずは、データ構造。
struct node
はグラフのノードを表し、フィールド s, t
がノードへの参照を値として持つことは,そのノードから参照先ノードへのエッジ(edge)が存在することを示している(NULL
値の場合は対応エッジはない).
id
はノードの識別子であり, visited
はノードの訪問回数を示す.
typedef struct node {
struct node * s;
struct node * t;
int id;
int visited;
} node_t, * node_tp;
#define BUFSIZE 100
struct node nodes[BUFSIZE];
一方で、探索プログラムはこんな感じ。
再帰的に探索をおこなうが、1度たどったところは、2度以上探索しないようにしています。
エッジは、s
→ t
の順で調べていきます。
void dfs(node_tp node) {
// node_tp s = node;
node->visited++;
printNode(node); // ノード表示用関数
if(node->visited == 1) {
node_tp s = node->s;
node_tp t = node->t;
if(s != NULL) dfs(s);
if(t != NULL) dfs(t);
}
}
で下記が、グラフを作成してから探索を行っている部分。
void initNodes(int n) {
int i;
for(i = 0; i<n; i++) {
nodes[i].id = i; nodes[i].visited = 0;
nodes[i].s = nodes[i].t = NULL;
}
}
void link(node_tp node, node_tp s, node_tp t) {
node->s = s; node->t = t;
}
void test1(void) { /* 2021 version */
initNodes(4);
link(&nodes[0], &nodes[2], &nodes[1]);
link(&nodes[1], &nodes[2], &nodes[3]);
link(&nodes[2], NULL, &nodes[3]);
link(&nodes[3], &nodes[0], NULL);
dfs(&nodes[0]); /* ノード 0 から探索 */
}
例えば、test1()
の場合、以下のようなグラフができているはず。
さて、以下が課題になります。
問題1
test1() を実行した際の実行結果を確認しましょう。
int main(void) {
test1();
return 0;
}
その上で、関数の Call Stack がどのように変化しながらプログラム実行が進んでいたか、コメント風に記述しなさい。 冒頭部だけ書くと、こんな感じ。
(0, 1) // stack:0
(2, 1) // stack:0:2
(3, 1) // stack:0:2:3
(0, 2) // stack:0:2:3:0
(1, 1) // stack:0:1
(2, 2)
(3, 2)
// stack:..
の部分は、頭で考えてもらっても良いし、デバッガでprintNodes()
に break point をいれて、調べても良いし、以下の option 課題を解くことで実現しても良いです。
オプション課題
上記 //stack:...
部分を自動で生成できるようにプログラムを拡張しなさい。
データ構造としての stack を自分で生成すれば OK です。
オプション課題なので、全員がとかなくても大丈夫。
問題2
こちらは、全員トライしましょう。
dfs 関数中の if 文を以下のように書き換えたとします。
void dfs(node_tp node) {
// node_tp s = node;
node->visited++;
printNode(node); // ノード表示用関数
if(1) { // 変更点! 常に then 節を実行
node_tp s = node->s;
node_tp t = node->t;
if(s != NULL) dfs(s);
if(t != NULL) dfs(t);
}
}
つまり、同じノードを何度でも探索しなおすこととします。
このとき test2 を実行した際の nodes[10]
の訪問回数は、どうなるでしょう?
void test2(void) {
int i;
initNodes(12);
for(i=0; i<10; i++)
link(&nodes[i], &nodes[i+1], &nodes[i+2]);
dfs(&nodes[0]); /* ノード 0 から探索 */
}
真面目に手でやると大変なんですが、実は、nodes[10]
の訪問回数は fib(10)
に一致します。
理由を考え、簡単に答えましょう。
ちなみに、fib(n) はフィボナッチ関数のことで、
int fib(int n) {
if(n==0 || n==1) return 1;
return fib(n-1)+fib(n-2);
}
で求まる関数とします。
課題提出
レポートは、plain text もしくは pdf で作成し、Beef から提出してください。
オプション課題を解いた人は、プログラムも提出すること。
課題の提出期限は、10/22 にします。まあ、少しぐらい遅れても受けとりますが、課題2以降を考えると、引っ張らない方がよいでしょう。