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

use strict; use warnings;
my %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];
my $start = 1;
my %visited = ();
$visited{$start} = 1;
my @queue = ($start);
my @order = ();
my $head = 0;
while ($head < scalar @queue) {
	my $v = $queue[$head];
	$head = $head + 1;
	push @order, $v;
	my $neighbours = $adj{$v};
	my $i = 0;
	while ($i < scalar @$neighbours) {
		my $nb = $neighbours->[$i];
		if (!exists $visited{$nb}) {
			$visited{$nb} = 1;
			push @queue, $nb;
		}
		$i = $i + 1;
	}
}
print "[" . join(", ", @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

Perl: a %adj hash of integer keys to array references is the idiomatic adjacency list and keeps the vertex iteration shape visible; the lesson keeps the queue as a plain @queue with a $head cursor rather than reaching for Thread::Queue or a Set::Object queue wrapper.
A %visited hash mapping vertex to 1 is the explicit "visited" set; using a Set::Object from CPAN would require an external dependency 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 A plain `@queue` plus a monotonically advancing `$head` index implements FIFO without the O(n) cost of `shift @queue` and without hiding the iteration shape behind a wrapper class.

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