深さ優先探索と幅優先探索 (dfs=Depth First Search) (bfs=Breadth First Search)

dfs_bfs.scala

import scala.collection.immutable.{Stack, Queue}
import scala.annotation.tailrec

case class Graph(es: Map[Vertex, Seq[Edge]])
case class Vertex(i: Int)
case class Edge(v: Vertex)

def sampleGraph: Graph = Graph(
  Map(
    Vertex(3) -> Seq(Edge(Vertex(1)), Edge(Vertex(2))),
    Vertex(1) -> Seq(Edge(Vertex(5)), Edge(Vertex(4))),
    Vertex(2) -> Seq(Edge(Vertex(6)))
  )
)

// 深さ優先探索 (Stack)
//       |3|
//   |1|     |2|
// |5| |4| |6|
//
// 3>1>5>4>2>6の順に探索
// start : 3
// goal  : 6
//
// stack[3]
// 3 : stack[1,2]
// 1 : stack[5,4,2]
// 5 : stack[4,2]
// 4 : stack[2]
// 2 : stack[6]
// 6
def dfs(g: Graph, v: Vertex, goal: Vertex): Boolean = {
  dfs(g, goal, Set(), Stack(v))
}
@tailrec
def dfs(g: Graph, goal: Vertex, visited: Set[Vertex], stack: Stack[Vertex]): Boolean = {
  val (v, s) = stack.pop2; println(s"v:${v} s:${s}")
  if (v == goal) true
  else if (visited.contains(v)) false
  else {
    g.es.get(v) match {
      case Some(e) => dfs(g, goal, visited + v, s.pushAll(e.reverseMap(_.v)))
      case _ if s.nonEmpty => dfs(g, goal, visited + v, s)
      case _ => false
    }
  }
}

// 深さ優先探索 (再帰)
def dfsRec(g: Graph, v: Vertex, goal: Vertex, visited: Set[Vertex] = Set()): Boolean = {
  println("v:" + v)
  if (v == goal) true
  else if (visited.contains(v)) false
  else g.es.get(v).exists(_.exists(e => dfsRec(g, e.v, goal, visited + v)))
}

// 幅優先探索
//       |3|
//   |1|     |2|
// |5| |4| |6|
//
// 3>1>2>5>4>6の順に探索
//
// queue[3]
// 3 : queue[1,2]
// 1 : queue[2,5,4]
// 2 : queue[5,4,6]
// 5 : queue[4,6]
// 4 : queue[6]
// 6
def bfs(g: Graph, v: Vertex, goal: Vertex): Boolean = {
  bfs(g, goal, Set(), Queue(v))
}
@tailrec
def bfs(g: Graph, goal: Vertex, visited: Set[Vertex], queue: Queue[Vertex]): Boolean = {
  val (v, q) = queue.dequeue; println(s"v:${v} s:${q}")
  if (v == goal) true
  else if (visited.contains(v)) false
  else {
    g.es.get(v) match {
      case Some(e) => bfs(g, goal, visited + v, e./:(q){(qq, ee) => qq.enqueue(ee.v)})
      case _ if q.nonEmpty => bfs(g, goal, visited + v, q)
      case _ => false
    }
  }
}