Depth-First Search (Recursive)

Visit a start vertex, then recurse into its first unvisited neighbour all the way down before backtracking. A visited set prevents revisiting, and neighbour insertion order fixes the visit sequence.

Algorithm

On the canonical 6-vertex graph from graph-adjacency-list, starting at vertex 1, the deterministic visit order is [1, 2, 4, 3, 5, 6]. Calls unwind 6 -> 5 -> 4 -> 3 -> 2 -> 1 after all vertices are visited.

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 visited = {}
local order = {}
local function dfs(v)
	visited[v] = true
	order[#order + 1] = v
	for i = 1, #adj[v] do
		local nb = adj[v][i]
		if not visited[nb] then
			dfs(nb)
		end
	end
end
dfs(1)
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) recursion depth

Implementation notes

Lua: a local function dfs recurses over the shared visited and order tables.
The replay shows the current vertex, the visited set, the running visit order, and the call stack after each entry, matching the lesson spec.

recursive descent Follow one branch to its end, then unwind and try the next neighbour.