夏に悩ましいことといえば暑さだけではありません。蚊です。蚊が厄介な点を少しばかり列挙してみます。

1. 暗闇に紛れて刺しにくるので、人間はハンデを負いつつ闘うことを余儀なくされる。
2. なぜか耳元で飛び回り睡眠妨害してくる。
3. 灯りをつけると物陰に隠れるので、起きた労力が無駄になる。骨折り損。
4. 網戸をしてもどこからか侵入してくる。
5. 叩くと家具や壁に血痕がのこる危険がある。
6. 病気を媒介する蚊もいる。
7. 蚊を追い払う製品が多すぎてどれがよいのかわからない。

こんなところでしょうか。まだあるかもしれません。なんで耳の周りを飛ぶんでしょうね。私は家具を汚したり騒音を出さないために、なるべく宙で鷲掴みにして対処しています。慣れてくるとほぼ百発百中になりますよ。手が少し濡れているとさらに容易に掴めます。

さて、今回は幅優先探索(BFS: Breadth-First Search)を使う問題をC言語で実装していきます。幅優先探索はグラフ探索の手法のひとつで、始点から近いところを優先的に探索します。以下にわかりやすい説明があります:

もうひとつ深さ優先探索というのがあります。こちらは猪突猛進、ぐいぐい進んで、壁にあたったら引き返し方向を変えてまた突進を繰り返すアルゴリズムです。二つの手法の比較は以下のリンクから:

今回の問題はこの幅優先探索を用いるのですが、C言語での実装例があまりないので、このnoteでシェアします。

1. 問題

ある洞窟にはN個の部屋とM個の通路があり、各通路は二つの異なる部屋を結んでいます。要するに部屋の集合がグラフを作っている。通路はそのグラフの辺、部屋はノードです。洞窟内部は危険なので、部屋1(出口につながる)に最短距離でたどり着けるように、各部屋に別の部屋番号を指し示した看板を立てたい。そのような看板が実際にたてられるなら、具体的なたて方を出力する問題です。

2. 方針

部屋１からどの部屋へも、ある経路が存在して到達可能だとします。部屋１から最短tステップで到達可能な部屋の集合をS(t)とします。(S(0) = {1}と定義します。)するとある部屋がS(t)に属しているとき、そこから最短で部屋１にたどり着くには、辺をたどって順にS(t-1), S(t-2), …, S(1), S(0)のなかの任意の部屋を進めばよい。問題はそれがいつでも可能かどうかです。

実は以下の命題を示すことができます。

S(t)の任意の部屋は、少なくともひとつのS(t-1)の部屋と通路で繋がっている。

もしそうでないとすると、つまりS(t)内にある部屋が存在して、どのS(t-1)内の部屋とも繋がっていないとすると、S(t)内の部屋がもつ、部屋１から最短tステップでたどり着けるという性質に反します。かなりあたりまえです。tステップである部屋にたどり着けるなら、t-1ステップ目に踏み入れた部屋と繋がっていないとおかしいですよね。

よってすべての部屋を部屋１からの距離(これは最短距離という意味)で層別し、S(t)の部屋にはS(t-1)の部屋のうちで繋がっているものを看板に表示すればいいことになります。なので答えは一通りではありません。

なお以下の実装では、部屋１から到達可能でない部屋はないと仮定します。

3. 実装

始めにstdio.hとstdlib.hをインクルードするのを忘れずに。

int main(){
	int N, M;
	scanf("%d %d", &N, &M);
	int *node[N+1], n_edge[N+1];
	for(int i = 0; i <= N; i++){
		node[i] = NULL;
		n_edge[i] = 0;
	}
	//グラフのデータベースを作成
	for(int m = 1; m <= M; m++){
		int i, j, *tmp;
		scanf("%d %d", &i, &j);
		n_edge[i]++;
		n_edge[j]++;

		node[i] = (int *) realloc(node[i], sizeof(int) * n_edge[i]);
		if(node[i] == NULL){
			printf("allocation_failure\n");
			return 1;
		}
		node[i][n_edge[i]-1] = j;

		node[j] = (int *) realloc(node[j], sizeof(int) * n_edge[j]);
		if(node[j] == NULL){
			printf("allocation_failure\n");
			return 1;
		}
		node[j][n_edge[j]-1] = i;
	}
	
	//start->endが始点から等距離にあるノード層
	//vacantはqueueの最初の空き場所
	int start = 1, end = start, vacant = 2;
	int queue[N+1], state[N+1];
	for(int i = 1; i <= N; i++)
   	    state[i] = -1;
	queue[1] = 1;
	state[1] = 1;
	while(start <= end){
		for(int current = start; current <= end; current++){
			int base = queue[current]; 
			for(int i = 0; i < n_edge[base]; i++){
				int neighbor = node[base][i];
				if(state[neighbor] < 0){
					queue[vacant] = neighbor;
					state[neighbor] = base;
					vacant++;
				}
			}
		}
		start = end + 1; 
		end = vacant - 1;
	}
	printf("Yes\n");
	for(int n = 2; n <= N; n++)
		printf("%d\n", state[n]);
	for(int i = 0; i <= N; i++)
		free(node[i]);
	return 0;
}

コードは大きく二つのパートからなります。まずグラフをデータベースに格納している部分。そしてそのあとに、グラフ内を幅優先探索し、部屋１からの距離に応じて看板に表示する部屋を計算している部分。

第一のデータベース化の部分では、stdlib.hに含まれるrealloc関数が核になっています。これは配列を動的に再割り当てする関数であり、ここではnode[i]に部屋iと繋がるすべての部屋を格納していくのに使います。各部屋によって繋がる部屋の数が異なるので、その数をn_edge[i]に格納しています。realloc関数はヌルポインタを渡すとmalloc関数と同じ働きをします。そこで最初にnode[i]をNULLで初期化しています。

注意点として、realloc関数を使う際は、再割り当てに失敗したときを考慮しなければなりません。メモリリークが発生するからです。私は以下のサイトを参考にしました。

次に部屋１からの最短距離を求める部分では、queueという配列を用意し、ここに探索候補を見つかった順に格納しています。先ほどの記号を使えば、S(0), S(1), S(2), …の順に部屋番号が格納されていきます。stateという配列は看板に表示する部屋番号を格納するもので、最初は-1で初期化され、同時に未探索のフラグの役目を果たします。看板に部屋番号が書き込まれると、探索済みの部屋となり、queueには重複して現れないようになっています。

ループを制御しているstartとendという変数は、部屋１から等距離にある部屋がqueueのどこからどこに格納されているかを記述しています。今回の問題では要りませんが、これによって各部屋に部屋１からの距離を割り当てることもできます。

4. 感想

アルゴリズムってわかってしまうと当たり前なんだけど、知らないとすごく損なんですよね。まずどんなアルゴリズムがあるかを知った上で、特定の問題にそれをどう使うかを考えるのが上達の早道ということでしょうか。

あと、自分のPCに開発環境を構築しようか悩んでいます。研究していたときはCygwin+Eclipseだったので、そこから始めようかな。オフラインでコンパイル&デバッグしたい。