幅優先探索について

幅優先探索では始めのノードから放射上に探索していく。具体的には下記のような感じになる。赤字が探索順だと思ってください。

木構造の場合


木構造の場合はこんな感じ。

グラフの場合


グラフの場合はこんな感じ。

特徴


重みのないグラフの最短経路を求めるのに利用できる。重みのあるグラフの最短経路を求めるにはダイクストラ法を使う。

実装


順番にキューに突っ込んでいく。今回はグラフを例にする。前述のグラフを例にすると、下記のような順でキューにエンキュー(キューに突っ込む)・デキュー(キューから取り出す)をしていく。

  • Aをエンキューする
  • Aをデキューする
  • Aと目的のノードと比較し、一致しない場合はB, C, Dをキューに入れる
  • Bをデキューする
  • Bを目的のノードと比較し、一致しない場合はFをエンキューする
  • 目的のノードが見つかるか、キューが空になるまで繰り返す

要するに見つからなければそのノードの隣接ノードをキューに突っ込んで比較していく。それを繰り返す。

注意点として、グラフの場合は一度訪問したノードを再度訪問するのは無駄 & 無限ループになる場合があるので、訪問済みノードも管理する必要があるという点。

計算量


  • キューへ一つ追加するのが $O(1)$
  • 頂点の個数はV(Vertex)として表す。これは $O(V)$ となる
  • 辺の個数はE(Edge)として表す。 これは $O(E)$ となる

両方を足すので $O(V + E)$ となる。

Scalaで実装


Scalaで実装してみるとこんな感じになった。printlnなどを書いているとはいえエライ汚いのだが、Scala片手間IT事務員おじさんにはこれが限界である。しかし、実装は(たぶん)間違ってないし、コードを綺麗に書くのが目的でもないのでとりあえずのところはコレで良いものとする。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import scala.collection.mutable

object BreadthFirstSearch extends App {

case class Node(name: String)

val sampleGraph: Map[Node, Seq[Node]] = Map(
Node("A") -> Seq(Node("B"), Node("C"), Node("D")),
Node("C") -> Seq(Node("E"), Node("F")),
Node("B") -> Seq(Node("F")),
Node("D") -> Seq(Node("G"), Node("H")),
Node("E") -> Seq(Node("J")),
Node("F") -> Seq(Node("I")),
Node("G") -> Seq(Node("J")),
Node("H") -> Seq()
)

val queue = new mutable.Queue[Node]
queue.enqueue(Node("A"))
bfs(sampleGraph, Node("G"), Seq())

def bfs(graph: Map[Node, Seq[Node]], goal: Node, visited: Seq[Node]): Boolean = {
if (queue.isEmpty) {
println("Not Found")
return false
}

val q = queue.dequeue()
println(s"$q $queue")
if (q == goal) {
println("Found")
return true
}

if (visited.contains(q)) {
bfs(graph, goal, visited)
} else {
graph.get(q) match {
case Some(x) => {
x.foreach(y => queue.enqueue(y))
bfs(graph, goal, visited :+ q)
}
case _ => bfs(graph, goal, visited :+ q)
}
}
}

}

/*
Node(A) Queue()
Node(B) Queue(Node(C), Node(D))
Node(C) Queue(Node(D), Node(F))
Node(D) Queue(Node(F), Node(E), Node(F))
Node(F) Queue(Node(E), Node(F), Node(G), Node(H))
Node(E) Queue(Node(F), Node(G), Node(H), Node(I))
Node(F) Queue(Node(G), Node(H), Node(I), Node(J))
Node(G) Queue(Node(H), Node(I), Node(J))
Found
*/

おわり。

参考書籍


なっとく! アルゴリズム