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.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";

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.