探索アルゴリズム (4)

前回の深さ優先探索に続いて今回は幅優先探索を紹介します。
幅優先探索 (Breadth First Search) はノードの子孫の中から世代が近い者を優先して探索していくアルゴリズムで、最短経路探索などに使われます。

このアルゴリズムの手順は以下のようになります。

1.探索中のノードを格納するキューを用意する
2.探索のルートとなるノードをキューに格納する
3.キューが空なら終了する
4.キューからノードを一つ取り出す
5.そのノードの子ノードをすべてキューに格納する
6.ノードに必要な処理を行う
7.3. に戻る
以下は Java のサンプルコードです。
このサンプルではツリー構造ではなく循環参照のあるグラフ構造に対して幅優先探索を行っているため、無限ループとならないようにチェックしているコードが追加されていますが、本質は同じです。

search/graph/BFS.java

package search.graph;


import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;


public class BFS {
	
	public static void main(String[] args) {
		Graph fortran = new Graph("Fortran");
		Graph algol = new Graph("Algol");
		Graph pli = new Graph("PL/I");
		Graph scheme = new Graph("Scheme");
		Graph c = new Graph("C");
		Graph cpp = new Graph("C++");
		Graph perl = new Graph("Perl");
		Graph tcl = new Graph("Tcl");
		Graph smalltalk = new Graph("Smalltalk");
		Graph pascal = new Graph("Pascal");
		Graph commonlisp = new Graph("Common Lisp");
		Graph java = new Graph("Java");
		Graph python = new Graph("Python");
		Graph csharp = new Graph("C#");
		Graph javascript = new Graph("JavaScript");
		Graph ruby = new Graph("Ruby");
		Graph ada = new Graph("Ada");
		Graph eiffel = new Graph("Eiffel");
		
		fortran.addChild(algol);
		fortran.addChild(pli);
		algol.addChild(scheme);
		algol.addChild(pascal);
		algol.addChild(c);
		algol.addChild(cpp);
		algol.addChild(perl);
		algol.addChild(tcl);
		scheme.addChild(commonlisp);
		cpp.addChild(java);
		java.addChild(javascript);
		java.addChild(csharp);
		cpp.addChild(csharp);
		cpp.addChild(python);
		c.addChild(cpp);
		c.addChild(python);
		algol.addChild(perl);
		perl.addChild(ruby);
		python.addChild(ruby);
		smalltalk.addChild(ruby);
		pli.addChild(pascal);
		pascal.addChild(python);
		pascal.addChild(ada);
		ada.addChild(eiffel);
		
		for (String lang : fortran)
			System.out.println(lang);
	}
	
	public static class Graph implements Iterable {
		
		private E value;
		private List> children;
		
		public Graph(E value) {
			this.value = value;
			this.children = new ArrayList>();
		}

		public void addChild(Graph child) {
			children.add(child);
		}

		@Override
		public Iterator iterator() {
			return new GraphIterator(this);
		}
		
		private static class GraphIterator implements Iterator {
			
			private Queue> open;
			private Set> closed;

			public GraphIterator(Graph tree) {
				open = new LinkedList>();
				open.offer(tree);
				closed = new HashSet>();
			}
			
			@Override
			public boolean hasNext() {
				return !open.isEmpty();
			}

			@Override
			public E next() {
				Graph t = open.poll();
				closed.add(t);
				for (Graph v : t.children)
					if (closed.add(v))
						open.offer(v);
				return t.value;
			}

			@Override
			public void remove() {
				throw new UnsupportedOperationException();	
			}	
		}
	}
}

2010年6月8日 | カテゴリー：アルゴリズム