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.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 start = 1
local visited = {}
visited[start] = true
local queue = {start}
local order = {}
local head = 1
while head <= #queue do
	local v = queue[head]
	head = head + 1
	order[#order + 1] = v
	local neighbours = adj[v]
	local i = 1
	while i <= #neighbours do
		local nb = neighbours[i]
		if not visited[nb] then
			visited[nb] = true
			queue[#queue + 1] = nb
		end
		i = i + 1
	end
end
io.write("[")
for k = 1, #order do
	if k > 1 then io.write(", ") end
	io.write(tostring(order[k]))
end
io.write("]\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

Lua: adj is a table keyed by integer vertex with sequence-style neighbour lists. The lesson keeps the queue as a table plus a head cursor rather than reaching for table.remove(queue, 1), so the enqueue / dequeue moves stay explicit and avoid the O(n) reshuffle that the stdlib helper would impose.
A visited table is the explicit "visited" set keyed by vertex id (visited[nb] returns nil for absent keys); the queue grows via queue[#queue + 1] = 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}` table 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.