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

<?php
$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 < count($queue)) {
	$v = $queue[$head];
	$head = $head + 1;
	$order[] = $v;
	$neighbours = $adj[$v];
	$i = 0;
	while ($i < count($neighbours)) {
		$nb = $neighbours[$i];
		if (!array_key_exists($nb, $visited)) {
			$visited[$nb] = true;
			$queue[] = $nb;
		}
		$i = $i + 1;
	}
}
echo "[" . implode(", ", $order) . "]\n";

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

PHP: $adj is an associative array keyed by integer vertex with plain-array neighbour lists. The lesson keeps the queue as an array plus a $head cursor rather than reaching for SplQueue, so the enqueue / dequeue moves stay explicit.
A $visited associative array is the explicit "visited" set (array_key_exists($nb, $visited)); the queue grows via $queue[] = $nb; to keep the append visible.
The replay prints the dequeued vertex, the queue, the visited set, and the running visit order each frame.

queue A plain `$queue = [$start];` array with an integer `$head` cursor 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.