Blog BFS top down

top-down.scala

class BFS(g: Graph) {

  val parent = ArrayBuffer.fill(g.numberVertices)(-1).toArray

  def bfs(source: Int, updater: (Seq[Int], Array[Int]) => Seq[Int]) = {
    var frontier = Seq(source)
    parent(source) = -2

    while (!frontier.isEmpty) {
      frontier = updater(frontier, parent)
    }
  }
}

trait TopDownUpdater extends FrontierUpdater {

  def update(frontier: Seq[Int], parents: Array[Int]): Seq[Int] = {
    val next = ArrayBuffer[Int]()

    frontier.foreach{ node =>
      graph.getNeighbors(node).filter(parents(_) == -1).foreach { neighbor =>
        next += neighbor
        parents(neighbor) = node
      }
    }
    next
  }