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

adj = {}
adj[1] = [2, 3]
adj[2] = [1, 4]
adj[3] = [1, 4]
adj[4] = [2, 3, 5]
adj[5] = [4, 6]
adj[6] = [5]
start = 1
visited = {}
visited[start] = true
queue = [start]
order = []
head = 0
while head < queue.length
	v = queue[head]
	head = head + 1
	order << v
	neighbours = adj[v]
	i = 0
	while i < neighbours.length
		nb = neighbours[i]
		if !visited.key?(nb)
			visited[nb] = true
			queue << nb
		end
		i = i + 1
	end
end
puts order.inspect

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

Ruby: a Hash of Integer -> Array(Integer) is the idiomatic adjacency list and keeps the vertex iteration shape visible; the lesson keeps the queue as an Array with a head cursor rather than reaching for Thread::Queue or a Set queue wrapper.
A Hash mapping vertex to true is the explicit "visited" set; using Set.new from set would require an extra require and hide the membership test behind a wrapper.
The replay prints the dequeued vertex, the queue, the visited set, and the running visit order each frame.

queue An `Array` plus a monotonically advancing `head` index implements FIFO without the O(n) cost of `Array#shift` and without hiding the iteration shape behind a stdlib queue class.

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