DFS

Depth-First Search traversal algorithms.

DFS explores a graph by going as deep as possible along each branch before backtracking. It is the basis for cycle detection, topological sorting, and strongly connected component algorithms (see Connectivity and TopologicalSort).

All implementations here are iterative (stack-based) rather than recursive, avoiding stack-overflow issues on large graphs.

All functions accept either callback form for GetNeighbors — see GraphUtil for details.

Example graph

--  A ──→ B ──→ D
--  │
--  ↓
--  C ──→ E

local adj = {
    A = {"B", "C"},
    B = {"D"},
    C = {"E"},
    D = {},
    E = {},
}

local function getNeighbors(v)
    return adj[v]
end

DFS traversal order

Because the iterative stack reverses insertion order relative to visited order, the traversal visits the last neighbour listed first. This differs from recursive DFS which visits the first neighbour first. If a specific neighbour order matters, sort the neighbour list before returning it from getNeighbors.

Functions

toArray

directedundirected

</>

DFS.toArray(

start: V,

getNeighbors: GetNeighbors<V>

) → {V}

Visits every vertex reachable from start in depth-first order and returns them as an ordered array.

local visited = DFS.toArray("A", getNeighbors)
-- e.g. { "A", "C", "E", "B", "D" }

Time complexity: O(V + E)

toSet

directedundirected

</>

DFS.toSet(

start: V,

getNeighbors: GetNeighbors<V>

) → {[V]: boolean}

Visits every vertex reachable from start in depth-first order and returns a set { [V]: true } of all visited vertices.

local reachable = DFS.toSet("A", getNeighbors)
print(reachable["D"]) -- true
print(reachable["Z"]) -- nil (unreachable)

Time complexity: O(V + E)

toIterator

directedundirected

</>

DFS.toIterator(

start: V,

getNeighbors: GetNeighbors<V>

) → KIterator<V>

Returns a lazy iterator that yields vertices one at a time in depth-first order. The iterator drives the DFS internally via a closure — no coroutines are used.

Aliased as DFS.forEach.

local next = DFS.toIterator("A", getNeighbors)
print(next()) -- "A"
print(next()) -- first deep branch vertex
-- ...
print(next()) -- nil  (exhausted)

for-loop usage

for vertex in DFS.toIterator("A", getNeighbors) do
    print(vertex)
end

Time complexity per call: amortised O(degree(V))

forEach

directedundirected

</>

DFS.forEach(

start: V,

getNeighbors: GetNeighbors<V>

) → KIterator<V>

Alias of DFS.toIterator.

toParentMap

directedundirected

</>

DFS.toParentMap(

start: V,

getNeighbors: GetNeighbors<V>

) → {[V]: V}

Performs a full DFS from start and returns a parent map — a table where every reachable vertex maps to the vertex it was discovered from. The start vertex maps to itself.

Useful for reconstructing the DFS spanning tree or testing reachability across all targets in one pass:

local function pathTo(parentMap, start, goal)
    if not parentMap[goal] then return nil end  -- unreachable
    local path = {}
    local v = goal
    while v ~= start do
        table.insert(path, 1, v)
        v = parentMap[v]
    end
    table.insert(path, 1, start)
    return path
end

local parents = DFS.toParentMap("A", getNeighbors)
print(pathTo(parents, "A", "E"))  -- e.g. { "A", "C", "E" }

Not shortest path

DFS parent maps do not guarantee shortest (fewest-hop) paths. Use BFS.toParentMap or BFS.shortestPath when hop-count matters.

Time complexity: O(V + E)