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.kt

fun main() {
	val adj = HashMap<Int, List<Int>>()
	adj[1] = listOf(2, 3)
	adj[2] = listOf(1, 4)
	adj[3] = listOf(1, 4)
	adj[4] = listOf(2, 3, 5)
	adj[5] = listOf(4, 6)
	adj[6] = listOf(5)
	val start = 1
	val visited = HashSet<Int>()
	visited.add(start)
	val queue = ArrayDeque<Int>()
	queue.addLast(start)
	val order = mutableListOf<Int>()
	while (queue.isNotEmpty()) {
		val v = queue.removeFirst()
		order.add(v)
		val neighbours = adj[v]!!
		for (i in neighbours.indices) {
			val nb = neighbours[i]
			if (!visited.contains(nb)) {
				visited.add(nb)
				queue.addLast(nb)
			}
		}
	}
	println(order.joinToString(prefix = "[", postfix = "]"))
}

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

Kotlin: HashMap<Int, List<Int>> is the idiomatic adjacency list and keeps the vertex iteration shape visible; the lesson keeps the queue as a plain ArrayDeque<Int> rather than reaching for Channel<T> or any coroutine wrapper.
A HashSet<Int> is the explicit "visited" set; the queue is the same ArrayDeque<Int> used elsewhere with removeFirst / addLast.
The replay prints the dequeued vertex, the queue, the visited set, and the running visit order each frame.

queue An `ArrayDeque<Int>` with `addLast` / `removeFirst` 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.