Shortest Path (Unweighted, via BFS)

BFS explores a graph layer by layer, so the first time it reaches a vertex is along a shortest path. Track dist[v] and parent[v] while exploring, then walk parents back from the target to reconstruct the route.

Algorithm

On the canonical graph from graph-adjacency-list, the shortest path from 1 to 6 is [1, 2, 4, 5, 6] with distance 4. The path is rebuilt from parent: 6 -> 5 -> 4 -> 2 -> 1, reversed.

Basic Implementation

basic.pl

use strict; use warnings;
my %adj = (
	1 => [2, 3],
	2 => [1, 4],
	3 => [1, 4],
	4 => [2, 3, 5],
	5 => [4, 6],
	6 => [5],
);
my $src = 1;
my $dst = 6;
my %dist = ($src => 0);
my %parent = ($src => 0);
my @queue = ($src);
my $head = 0;
while ($head < scalar @queue) {
	my $v = $queue[$head];
	$head = $head + 1;
	for my $nb (@{$adj{$v}}) {
		if (!exists $dist{$nb}) {
			$dist{$nb} = $dist{$v} + 1;
			$parent{$nb} = $v;
			push @queue, $nb;
		}
	}
}
my @path = ();
my $node = $dst;
while ($node != 0) {
	push @path, $node;
	$node = $parent{$node};
}
@path = reverse @path;
print "[" . join(", ", @path) . "]\n";
print "$dist{$dst}\n";

Complexity

Time: O(V + E)
Space: O(V)

Implementation notes

Perl: %dist doubles as the visited check, %parent records predecessors (0 marks the source), and a head index walks the @queue.
The replay shows dist, parent, and the queue filling in, then the reconstructed path, matching the lesson spec.

layers equal distance BFS order equals distance in an unweighted graph.