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]

with start 1 produces visit order [1, 2, 3, 4, 5, 6].

Basic Implementation

basic.swift

var adj: [Int: [Int]] = [:]
adj[1] = [2, 3]
adj[2] = [1, 4]
adj[3] = [1, 4]
adj[4] = [2, 3, 5]
adj[5] = [4, 6]
adj[6] = [5]
let start = 1
var visited: Set<Int> = []
visited.insert(start)
var queue: [Int] = []
queue.append(start)
var order: [Int] = []
while !queue.isEmpty {
	let v = queue.removeFirst()
	order.append(v)
	let neighbours = adj[v]!
	for i in neighbours.indices {
		let nb = neighbours[i]
		if !visited.contains(nb) {
			visited.insert(nb)
			queue.append(nb)
		}
	}
}
print(order)

Complexity

Time: O(V + E)
Space: O(V) for the queue plus the visited set

Implementation notes

Swift: var queue: [Int] with append / removeFirst plus var visited: Set<Int> is the smallest honest BFS shape. The stdlib Set<Int> is the idiomatic membership type without importing Foundation.
The adjacency list is a [Int: [Int]] to avoid hard-coded vertex count assumptions while keeping the canonical neighbour order from the spec.
The replay shows the queue contents, the visited set, and the running visit order on each dequeue frame.

queue A `[Int]` array used as a queue with `append` for enqueue and `removeFirst` for 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.