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

Canonical adjacency list:

1 -> [2, 3]
2 -> [1, 4]
3 -> [1, 4]
4 -> [2, 3, 5]
5 -> [4, 6]
6 -> [5]

Starting at vertex 1, the BFS visit order is [1, 2, 3, 4, 5, 6].

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("[", ", ", "]"))
	}
}

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.