Breadth-First Search

From a start vertex, explore the graph layer by layer. Use a queue and a "visited" set. Dequeue a vertex, visit it, enqueue all unvisited neighbours.

Algorithm

Basic Implementation

basic.scala

import scala.collection.mutable.{HashMap, HashSet, Queue, ArrayBuffer}

object Main {
	def main(args: Array[String]): Unit = {
		val adj = HashMap.empty[Int, List[Int]]
		adj(1) = List(2, 3)
		adj(2) = List(1, 4)
		adj(3) = List(1, 4)
		adj(4) = List(2, 3, 5)
		adj(5) = List(4, 6)
		adj(6) = List(5)
		val start = 1
		val visited = HashSet.empty[Int]
		visited += start
		val queue = Queue.empty[Int]
		queue.enqueue(start)
		val order = ArrayBuffer.empty[Int]
		while (queue.nonEmpty) {
			val v = queue.dequeue()
			order += v
			val neighbours = adj(v)
			for (i <- neighbours.indices) {
				val nb = neighbours(i)
				if (!visited.contains(nb)) {
					visited += nb
					queue.enqueue(nb)
				}
			}
		}
		println(order.mkString("[", ", ", "]"))
	}
}

BFS uses a queue, so it visits the start vertex, then its neighbours, then the next layer.

Step 1 - Start at 1

The queue starts with [1] and visited starts with {1}.

Step 2 - Visit the first layer

After processing 1, neighbours 2 and 3 are marked and queued.

Step 3 - Deterministic visit order

With insertion-ordered neighbours, BFS visits [1, 2, 3, 4, 5, 6].

Complexity

Time: O(V + E)
Space: O(V)

Implementation notes

Scala: HashMap[Int, List[Int]] is the idiomatic adjacency list and keeps the vertex iteration shape visible; the lesson keeps the queue as a plain scala.collection.mutable.Queue[Int] rather than reaching for scala.concurrent.Channel or any Akka actor wrapper.
A HashSet[Int] is the explicit "visited" set; the queue is the same mutable Queue[Int] used elsewhere with dequeue() / enqueue(...).
The replay prints the dequeued vertex, the queue, the visited set, and the running visit order each frame.

queue A `scala.collection.mutable.Queue[Int]` with `enqueue` / `dequeue` implements FIFO without hiding the iteration shape.

visited-before-enqueue Mark a vertex visited before pushing it onto the queue. Keeps the queue size bounded by V.