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

local 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}
local src = 1
local dst = 6
local dist = {}
local parent = {}
dist[src] = 0
parent[src] = 0
local queue = {src}
local head = 1
while head <= #queue do
	local v = queue[head]
	head = head + 1
	for i = 1, #adj[v] do
		local nb = adj[v][i]
		if dist[nb] == nil then
			dist[nb] = dist[v] + 1
			parent[nb] = v
			queue[#queue + 1] = nb
		end
	end
end
local path = {}
local node = dst
while node ~= 0 do
	path[#path + 1] = node
	node = parent[node]
end
io.write("[")
for k = #path, 1, -1 do
	if k < #path then io.write(", ") end
	io.write(tostring(path[k]))
end
io.write("]\n")
io.write(tostring(dist[dst]) .. "\n")

Complexity

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

Implementation notes

Lua: dist doubles as the visited check, parent records predecessors (0 marks the source), and a head index walks the queue table.
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.