逆転を狙う工大生の日々

絶賛留年中の落ちこぼれがなんとか頑張ろうとしている日記です

Javaで深さ優先探索と幅優先探索

とうとうやってまいりました。深さ優先探索幅優先探索。実装につきましては、以下のサイトを参考にさせていただきました。ありがとうございます。参考というかまんま・・・

http://d.hatena.ne.jp/lettas0726/20110418/1303097692

 今回は2分木で各探索を実現しましたが、2分木についての概要を簡単に

木構造の一種

・そもそも木構造とは?

→ 階層関係を実現するためのデータ構造。データを「節(ノード)」にもたせて、それを「枝(エッジ)」で繋ぐことで、各データの関係を階層的に表現することが出来る。一番上のノードを「」、あるノードAから見て、エッジで結ばれていて、かつ根に近いノードBのことを「BはAの親ノード」といい、逆に「AはBの子ノード」という。

・K分木とは、各ノードについて、その子ノードが最大でK個である木のこと

・つまり2分木は、各ノードの子ノードが最大2つである木

 

ふむふむ。度々習ってきたことなので概要だけならわかるぞ。いよいよ実装です。

2分木構造の表現


	BinaryTree left; //2分木の左の子ノード
	BinaryTree right; //右の子ノード
	Object data; //このノードのデータ
	
	//新たなノードを生成する
	public BinaryTree(Object data, BinaryTree left, BinaryTree right) {
		this.data = data;
		this.left = left;
		this.right = right;
	}    

2分木はこれで良さそうですね。これはリスト構造のnextと考え方はにてますね。

 

続いて、深さ優先探索についての概要を

・DFS(Depth First Search)

・始点からの距離には関係なく、訪問できる節を出来るだけ深く訪問していく探索法

・始点からどんどん深い階層にたどっていき、子ノードがないノードに到達したら、ひとつ前のノードに戻って再びそこからたどっていくという方法。

・スタックを用いて実現

 2分木だと、ずっと左の子ノードをたどっていき、子ノードが無くなったら、一つ前のノードの右の子ノードを訪れて同様にたどっていくという感じですね。バックトラックがこういう辿り方をするはずです。・・・ですよね?

DFSの実装

	//状況に合った子ノードを返す(DFS用)
	public BinaryTree[] getChildrenDfs(){
		if(left != null && right != null){
			BinaryTree[] o = {right,left};
			return o;
		}else if(left != null && right == null){
			BinaryTree[] o = {left};
			return o;
		}else if(left == null && right != null){
			BinaryTree[] o = {right};
			return o;
		}
		BinaryTree[] o = {};
		return o;
	}
	
	public void dfs(BinaryTree t,Object goal){
		ArrayDeque stack = new ArrayDeque();
		stack.push(t);
		while(!stack.isEmpty()){
			BinaryTree t1 = stack.pop();
			System.out.println(t1.data + "を訪れました");
			if(t1.data == goal){
				System.out.println("目標" + goal + "に到達しました");
				break;
			}
			for(BinaryTree t2 : t1.getChildrenDfs()){
				stack.push(t2);
			}
		}
	}

まずは、現在訪れているノードの子ノードを返す関数getChildrenDfs()について。まあ子ノードを返すだけです。左右ノードが存在するときに{right,left}とするのは、配列の先頭からスタックにプッシュするとき、この順番じゃないと右ノードから深くたどっていってしまうからです。深さ優先探索は、

1,スタックから要素をポップ

2,要素で何かする

3,子ノードをプッシュ

4,終了条件まで繰り返す

という思ったより簡単なアルゴリズムでした。多分覚えました。

 

続いて、幅優先探索の概要を

・BFS(Breath First Search)

・同じ階層の要素を左ノードからすべて探索した後、一つ下の階層にうつって同様にすべて探索する。これを繰り返す。

・キューを用いて実現する

こちらのほうが言葉で説明しやすいですねw 絶対に左ノードから辿る必要はないのかな?

BFSの実装

	//状況に合った子ノードを返す(BFS用)
	public BinaryTree[] getChildrenBfs(){
		if(left != null && right != null){
			BinaryTree[] o = {left,right};
			return o;
		}else if(left != null && right == null){
			BinaryTree[] o = {left};
			return o;
		}else if(left == null && right != null){
			BinaryTree[] o = {right};
			return o;
		}
		BinaryTree[] o = {};
		return o;
	}
	public void bfs(BinaryTree t,Object goal){
		ArrayDeque queue = new ArrayDeque();
		queue.offer(t);
		while(!queue.isEmpty()){
			BinaryTree t1 = queue.poll();
			System.out.println(t1.data + "を訪れました");
			if(t1.data == goal){
				System.out.println("目標" + goal + "に到達しました");
				break;
			}
			for(BinaryTree t2 : t1.getChildrenBfs()){
				queue.offer(t2);
			}
		}
	}

こちらでは子ノードを{left,right}の順番にしています。キューはFIFOなのでこうしないと右ノードからたどってしまいます。右ノードからでも良いとは思いますがね。DFSにおけるスタックがキューに変わっただけでこうなるとはなんか凄いですね。スタックもキューも使い方次第でこうも違うのかと。

実行結果

public class Main {
	public static void main(String[] args) {
		BinaryTree t = 
		new BinaryTree("S",new BinaryTree("a",new BinaryTree("c",null,null),
				new BinaryTree("d",null,null)),new BinaryTree("b",new BinaryTree(
				"e",null,null),new BinaryTree("f",null,null)));
				
		System.out.println("DFSの結果");
		t.dfs(t,"e");
		System.out.println("----------------------------------------");
		System.out.println("BFSの結果");
		t.bfs(t,"e");
	}
}

f:id:ikuth:20140514214232p:plain

この図のような木を生成します。そして各探索の結果を出力します。

f:id:ikuth:20140514214556p:plain

出来ました!!ちゃんとスタックやキューの中身も出力させたほうが良かったかなーと思いながら、紙とペンでその辺はしっかり手を動かしたので動きもつかめました。

 

なんとか更新間に合いました。疲れてて日中ずっとボケっとしてたツケが・・・。

 今期中はとりあえずJavaで色々やってこうと思います。CとかC++は暇になる来期にみっちりやってこうと・・・。

 

内容がしょっぱすぎて、プログラミングタグつけるの怖くなってきたけど許して。