BFS

Breadth-First Search traversal and unweighted shortest-path algorithms.

BFS explores a graph level-by-level outward from a start vertex, visiting all neighbours at the current depth before moving deeper. This property makes it the correct choice for unweighted shortest paths (fewest hops). For weighted shortest paths, use Dijkstra or AStar.

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

Example graph

--  A ─── B ─── D
--  │           │
--  C ──────────┘

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

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

Functions

toArray

directedundirected

</>

BFS.toArray(

start: V,

getNeighbors: GetNeighbors<V>

) → {V}

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

local visited = BFS.toArray("A", getNeighbors)
-- { "A", "B", "C", "D" }  (BFS level order)

Time complexity: O(V + E)

toSet

directedundirected

</>

BFS.toSet(

start: V,

getNeighbors: GetNeighbors<V>

) → {[V]: boolean}

Visits every vertex reachable from start in breadth-first order and returns a set { [V]: true } of all visited vertices. Useful when you only need a reachability check rather than the traversal order itself.

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

Time complexity: O(V + E)

toIterator

directedundirected

</>

BFS.toIterator(

start: V,

getNeighbors: GetNeighbors<V>

) → KIterator<V>

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

Aliased as BFS.forEach.

local next = BFS.toIterator("A", getNeighbors)
print(next()) -- "A"
print(next()) -- "B"
print(next()) -- "C"
-- ...
print(next()) -- nil  (exhausted)

for-loop usage

The iterator is compatible with a plain for loop since Luau supports for x in fn do for () -> T? iterators:

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

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

forEach

directedundirected

</>

BFS.forEach(

start: V,

getNeighbors: GetNeighbors<V>

) → KIterator<V>

Alias of BFS.toIterator.

shortestPath

directedundirected

</>

BFS.shortestPath(

start: V,

goal: V,

getNeighbors: GetNeighbors<V>,

shouldStop: ShouldStop<V>?

) → PathResult<V>?

Finds the shortest path (fewest hops / edges) from start to goal using BFS. Returns a PathResult where cost is the hop count, or nil if goal is unreachable from start.

This is the correct function to use when all edges have equal (or no) weight. For weighted shortest paths use Dijkstra.shortestPath.

local result = BFS.shortestPath("A", "D", getNeighbors)
-- result.path == { "A", "B", "D" }  (or { "A", "C", "D" })
-- result.cost == 2

Pass an optional ShouldStop predicate to abort a long-running search — checked once per dequeued vertex, receiving that vertex's hop-distance from start as cost. Returning true stops the search and returns nil:

-- Search no deeper than 6 hops.
local result = BFS.shortestPath("A", "D", getNeighbors, function(_vertex, depth)
    return depth >= 6
end)

Time complexity: O(V + E)

bidirectionalShortestPath

directedundirected

</>

BFS.bidirectionalShortestPath(

start: V,

goal: V,

getNeighbors: GetNeighbors<V>,

getReversedNeighbors: GetNeighbors<V>?,

shouldStop: ShouldStop<V>?

) → PathResult<V>?

Finds the shortest path (fewest hops) between start and goal by growing a BFS frontier from both ends simultaneously and stopping as soon as the two frontiers are provably guaranteed to have met at the shortest possible point. Returns the same PathResult as BFS.shortestPath, or nil if goal is unreachable.

On large, densely-branching graphs this explores far fewer vertices than a single-directional search — each side only needs to reach roughly half the hop-distance, so the total number of vertices visited grows with the branching factor to the power of half the distance instead of the full distance.

local result = BFS.bidirectionalShortestPath("A", "D", getNeighbors)
-- result.path == { "A", "B", "D" }  (or { "A", "C", "D" })
-- result.cost == 2

:::caution Directed graphs Growing a frontier backward from goal requires walking edges in reverse. By default this function reuses getNeighbors for both directions, which is only correct for undirected graphs. For a directed graph, pass a third callback that returns the predecessors of a vertex (i.e. getReversedNeighbors(v) returns every u such that u → v is an edge):

-- Directed graph where reverseAdj[v] lists v's predecessors
local function getReversedNeighbors(v)
    return reverseAdj[v]
end

local result = BFS.bidirectionalShortestPath("A", "D", getNeighbors, getReversedNeighbors)

:::

An optional ShouldStop predicate (passed after getReversedNeighbors) aborts the search and returns nil — it is checked each time either side dequeues a vertex, receiving that vertex's hop-distance from its own root as cost.

Time complexity: O(V + E) worst case, but typically O(b^(d/2)) for a graph with branching factor b and hop-distance d between start and goal.

toParentMap

directedundirected

</>

BFS.toParentMap(

start: V,

getNeighbors: GetNeighbors<V>

) → {[V]: V}

Performs a full BFS 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.

This gives you the BFS spanning tree in one pass, letting you reconstruct the shortest hop-path to any reachable vertex without running a separate search per target:

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 = BFS.toParentMap("A", getNeighbors)
print(pathTo(parents, "A", "D"))  -- { "A", "B", "D" }
print(pathTo(parents, "A", "C"))  -- { "A", "C" }

Time complexity: O(V + E)