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

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.