どうもー シュモクザメです。
今回からグラフの探索の実装の記事を書いてこうかなーって思ってます。
とりあえず第一弾は縦系探索です！
今回は簡単さを優先で、スタックなどを考えずに実装してみました！！
グラフの探索って？
とりあえず迷路を解くことを考えてみましょう。
迷路？
以下の迷路が解けますか？
んー まあ余裕すぎますよね。
一ミリも迷わんわな
しかし今回は人間が解くのではなく、
あるアルゴリズムを持たせたプログラムに解いてもらいます。
それが今回の探索です！！
迷路をグラフとして考える
とりあえず先ほどの迷路をプログラムが扱いやすいように変換します。
その時に使うのが状態遷移図です。
このようにそれぞれの状態（今回の場合は座標）を要素として、各状態を行き来できる場所（今回の場合は迷路の道）を辺としてグラフにしたものです。
この状態遷移図を用いて、アルゴリズムと実装を考えていきます！！
縦系探索のアルゴリズム
とりあえずアルゴリズムを紹介します。
形式的には、深さ優先探索は、探索対象となる木の最初のノードから、目的のノードが見つかるか子のないノードに行き着くまで、深く伸びていく探索である。その後はバックトラックして、最も近くの探索の終わっていないノードまで戻る。非再帰的な実装では、新しく見つかったノードはスタックに貯める。
(wikipedia 「深さ優先探索 概要 より引用」)
うーん… 文字だけだとわかりにくい…
ですよね〜
まあOPENリストやCLOSEリストなどを用いてこの説明通りに解説すると少しややこしくなるので、今回はあくまでコードを組むこと前提で簡単に説明してみます。
上の状態遷移図を以下のようにわかりやすくしてみました。
一番上がスタートの要素で、そこから辺を下に伸ばしています。（木構造ですね）
縦系探索ではこのグラフを以下のように探索します
なんとなく縦方向に大きく動きながら探索しているのがわかりますかね？
これが縦系の縦の意味です！！
そしてどのようなアルゴリズムで探索しているのかというと、
- スタート地点から進めるだけ進む
- もし行き止まりになったら、今まで通ってきた道で一番近い分岐点まで戻る
- そこから進めるだけ進む(行き止まりになったら2に戻る)
これだけです。簡単ですね。
つまり深さを優先してどんどん進んでいこうっていう感じですね。
コードの実装
隣接行列の導入
C言語でグラフを扱うために隣接行列というものを導入します。
隣接行列とは、要素がN個ある無向グラフにおいて
i番目の要素とj番目の要素が辺でつながれているなら(i,j)成分を1、そうでないなら0にしたNxN行列のことです。
上の状態遷移図の場合は以下のような隣接行列になります。
{{0,1,0,0,0,0,0,0,0},
{1,0,0,0,1,0,0,0,0},
{0,0,0,0,0,1,0,0,0},
{0,0,0,0,1,0,0,0,0},
{0,1,0,1,0,1,0,1,0},
{0,0,1,0,1,0,0,0,0},
{0,0,0,0,0,0,0,1,0},
{0,0,0,0,1,0,1,0,1},
{0,0,0,0,0,0,0,1,0}};縦系探索の関数
コンセプトは再帰呼び出しでどんどん進んでいく、です。
再帰呼び出しなら行き止まりにあたったら、処理を再帰しないようにすれば分岐点まで帰って来れるので便利ですね。
とりあえずコードです。
int flag[N]={0};
void VertSearch(int i)
{
int j;
flag[i] = 1;
for (j=0 ; j<N ; j++){
if (a[i][j] == 1 && flag[j] == 0){
printf("%d\n",j+1);
VertSearch(j);
}
}
}
まず引数です。
ここにいれた要素を起点に探索をしてきます。
なのでmainで最初に渡すときはスタートの要素を渡します。
そこからその要素がどの要素につながっているかを、隣接行列のその要素の行をfor文で走査していくことで調べます。
つながっていれば、今度はそのつながっている要素に対して縦系探索を実行します。
コードでいうif(a[i][j] == 1 && flag[j] == 0)のところですね。
ん？ifの条件文の中のflag[j]は何のこと？
この配列flagは各要素をすでに探索済みかを記録しておく配列です。
隣接行列を見てもらえば分かるように、このグラフは無向グラフなのでこの方法だと探索する要素が重複してしまいます。
なのでまず配列flagを用意して要素を全て0にし、
一度探索した要素に対応する配列flagの要素を1に変更していきます。
グローバル変数にして、どの再帰の中にいても共有して使えるようにしています。
つまりflagが0ならまだ探索してないからokですよってことね
実際につかってみた
実行してみました。
アルゴリズム解説で示した通りにいけましたね。
（ただ縦系探索だと無駄な寄り道をする可能性が高い..）
他の方法でグラフの探索する記事もそのうちかいてみたいと思います〜
ではまた。
全体のコード
#include <stdio.h>
#define N 9
int a[N][N]=
{{0,1,0,0,0,0,0,0,0},
{1,0,0,0,1,0,0,0,0},
{0,0,0,0,0,1,0,0,0},
{0,0,0,0,1,0,0,0,0},
{0,1,0,1,0,1,0,1,0},
{0,0,1,0,1,0,0,0,0},
{0,0,0,0,0,0,0,1,0},
{0,0,0,0,1,0,1,0,1},
{0,0,0,0,0,0,0,1,0}};
int flag[N]={0};
void VertSearch(int i)
{
int j;
flag[i] = 1;
for (j=0 ; j<N ; j++){
if (a[i][j] == 1 && flag[j] == 0){
printf("%d\n",j+1);
VertSearch(j);
}
}
}
int main(void)
{
printf("%d\n",1);
VertSearch(0);
return (0);
}
コメント