Graphs and Graph Algorithms Questions

Direct answer

Use an explicit stack and a visited set; check whether the popped node is the target BEFORE checking or updating visited state, so the function can return True the instant the target is discovered rather than waiting to fully process it. This early exit is the main performance lever over a full traversal, since for many queries the target is found long before the rest of the graph would have been explored.

Structured elaboration

Path existence between two nodes only needs a yes/no answer, so nothing about a full traversal's bookkeeping (discovery order, per-node results) is required. The traversal can stop the instant the target is popped from the stack, rather than finishing whatever level or subtree it happens to be in. A visited set still guards against revisiting nodes on graphs with cycles, exactly as in any other DFS, but the check for "is this the target" happens first, ahead of the visited check, so that even a target reachable through a cycle is caught immediately rather than only after normal traversal bookkeeping would have gotten to it.

Worked example

def has_path_iterative_dfs(graph, start, target):
    if start not in graph and start != target:
        return False
    if start == target:
        return True
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node == target:
            return True
        if node in visited:
            continue
        visited.add(node)
        for nbr in graph.get(node, []):
            if nbr not in visited:
                stack.append(nbr)
    return False

if __name__ == "__main__":
    graph = {
        "A": ["B", "C"],
        "B": ["D"],
        "C": ["D"],
        "D": ["A"],   # cycle back to A
        "E": ["F"],   # separate component, unreachable from A
        "F": [],
    }
    print("A -> D reachable:", has_path_iterative_dfs(graph, "A", "D"))
    print("A -> E reachable (different component):", has_path_iterative_dfs(graph, "A", "E"))
    print("A -> A trivial (same node):", has_path_iterative_dfs(graph, "A", "A"))
    print("Z -> A, Z missing from graph:", has_path_iterative_dfs(graph, "Z", "A"))

    # Early-exit proof: on a long chain, reaching the immediate neighbor of start
    # should not require expanding the rest of a huge unrelated subgraph.
    chain = {i: [i + 1] for i in range(100000)}
    print("Long chain of 100000 nodes, 0 -> 1 found:", has_path_iterative_dfs(chain, 0, 1))

Output (actually executed with python3):

A -> D reachable: True
A -> E reachable (different component): False
A -> A trivial (same node): True
Z -> A, Z missing from graph: False
Long chain of 100000 nodes, 0 -> 1 found: True

Complexity

• Worst case (target unreachable, or reachable only after exploring most of the graph): time $O(V + E)$, each node and edge examined at most once.
• Best case (target adjacent to start or found early): far less than a full traversal, the early exit on the node == target check returns as soon as the target is popped.
• Space: $O(V)$ for the visited set; stack size in the worst case also $O(V)$, bounded by the longest unexplored path currently pending.

Edge cases

• start == target: handled explicitly up front, returns True immediately without touching the graph at all.
• start missing from the graph entirely (not even a value somewhere): returns False immediately rather than attempting a lookup that would find nothing anyway.
• Empty graph: no nodes to explore, returns False unless start == target was already caught above.
• Very long chains: the early-exit test above uses a 100,000-node chain and confirms an immediate neighbor is found without materializing or fully walking the rest of the chain.

Trade-offs and pitfalls

• Common mistake: checking node in visited before checking node == target; if the target itself somehow ends up added to visited on an earlier pass through the loop (for instance, if the visited check were structured differently), the function could miss reporting it as found, ordering the target check first avoids this entirely.
• This function only answers existence, not the path itself. If the ACTUAL path is needed, track a parent-pointer map alongside the stack (came_from[neighbor] = node at push time) and reconstruct by walking came_from backward from the target once found.
• For REPEATED path-existence queries between many different pairs on the same static graph, computing connected components once (via a single traversal or union-find) and then answering each query as an O(1) "same component" check is far cheaper than re-running a fresh DFS per query.

Direct answer

A first-in-first-out (FIFO) queue drives breadth-first search (BFS) and explores a graph in layers, giving the shortest path by edge COUNT in an unweighted graph. A stack (last-in-first-out, LIFO) drives depth-first search (DFS) and dives along one path before backtracking, which is what topological sort, cycle detection, and general backtracking search need. A priority queue orders by cost rather than arrival order, and is what Dijkstra's algorithm and A* need to guarantee the cheapest path is finalized first in a weighted graph.

Structured elaboration

FIFO queue, BFS. Every node enqueued at layer $i$ is dequeued before any node at layer $i+1$ is examined, which is exactly why BFS finds the minimum-hop-count path in an unweighted graph: the first time a node is reached, it has been reached by the fewest possible edges. Complexity: $O(V+E)$ time, $O(V)$ memory for the visited set and queue.

Stack, DFS. A stack commits to exploring one branch as deep as possible before backtracking to try a sibling branch. This depth-first commitment is exactly what topological sort needs (finish a node's entire subtree, THEN place it), what cycle detection via color marking needs (a back edge to a node still "in progress," meaning still on the stack, signals a cycle), and what backtracking search over combinatorial spaces needs (commit, explore, undo if it fails). Complexity: $O(V+E)$ time; recursion depth (or explicit stack depth) up to $O(V)$ in the worst case, and a naive recursive implementation risks a stack overflow on a deep or adversarial graph, which is why production code often prefers an explicit stack.

Priority queue, Dijkstra and A.* Whenever edges have different positive weights, arrival ORDER (FIFO or LIFO) no longer corresponds to cost order, so the algorithm needs to always expand whichever frontier node currently has the lowest known cost, which is exactly what a priority queue (typically a binary heap) provides. Dijkstra's algorithm uses actual accumulated cost as the priority; A* adds a heuristic estimate of remaining cost to the goal, letting it prune the search toward the goal rather than expanding uniformly outward. Complexity: $O((V+E) \log V)$ with a binary heap, versus $O(V+E)$ for the unweighted structures, the $\log V$ factor is the price of maintaining cost order instead of arrival order.

Worked example

A service-dependency graph where each edge is a call with a latency cost. Three different questions about the same graph need three different structures:

1. "How many hops away is service X?" (a topology/blast-radius question, unweighted) -> FIFO queue, BFS. Answer comes out layer by layer, cheaply.
2. "Does this recent config change introduce a circular dependency?" -> stack, DFS with color marking; a back edge into a gray (in-progress) node during the DFS is the cycle, found without any notion of cost.
3. "What is the lowest-latency path from the edge gateway to this database?" -> priority queue, Dijkstra (or A* if a good latency-lower-bound heuristic to the destination is available, for example straight-line network distance). The FIFO/stack structures above would give a WRONG answer here, since a path with more hops but each individually low latency can beat a path with fewer hops but one very slow edge.

Trade-offs and pitfalls

• Common mistake: using a plain FIFO queue on a WEIGHTED graph expecting shortest-path-by-cost; BFS with a FIFO queue only gives shortest-path-by-EDGE-COUNT, which silently gives the wrong answer the moment edge weights differ.
• Common mistake: choosing a priority queue by default "to be safe" even when the graph is unweighted; this pays an unnecessary $\log V$ factor and added implementation complexity for no benefit, since a plain queue already gives the optimal answer for unweighted shortest paths.
• Heap choice matters at scale: a binary heap gives $O(\log V)$ per operation and is simple to implement; a Fibonacci heap gives an amortized $O(1)$ decrease-key, improving Dijkstra's total complexity to $O(E + V \log V)$, but the implementation complexity rarely pays off outside of very large, decrease-key-heavy workloads, most production systems use a binary heap.
• A double-ended queue (deque) is worth naming as a fourth option: it supports the 0-1 BFS variant (edge weights restricted to 0 or 1) by pushing 0-weight edges to the front and 1-weight edges to the back, giving Dijkstra-correct results at BFS's $O(V+E)$ speed for that restricted weight case, without needing a full priority queue.

Direct answer

Iterative deepening depth-first search (IDDFS) repeatedly runs a depth-limited depth-first search (DFS) with an increasing depth cutoff, 0, then 1, then 2, and so on, until the target is found. It combines depth-first search's low memory footprint (proportional to the current depth, not the whole frontier) with breadth-first search (BFS)'s guarantee of finding the shallowest solution first, without paying BFS's memory cost of holding an entire frontier layer in memory at once.

Structured elaboration

Why not just use plain DFS? Plain DFS can dive down an arbitrarily long, wrong branch before ever backtracking to try a shallow, correct one; it offers no guarantee of finding the shortest solution first, and on an infinite or very large search space it might never terminate on a branch that happens to have no solution.

Why not just use plain BFS? BFS does guarantee finding the shallowest solution, but it must hold the entire current frontier in memory, which grows as $O(b^d)$ for branching factor $b$ and depth $d$, the same as IDDFS's TIME complexity, but as memory. For a search space with a large branching factor, that memory requirement becomes the actual bottleneck long before time does.

What IDDFS trades to get both properties. Each depth-limited pass re-does all the work of every shallower pass (visiting depth 0, then 1, then 2 again inside the depth-2 pass, and so on), so IDDFS's total work is more than a single BFS pass, asymptotically the same order, $O(b^d)$, because the geometric sum of work across all depths up to $d$ is dominated by the final, deepest pass. In exchange, memory drops from $O(b^d)$ (BFS) to $O(d)$ (the depth of the current recursion stack), a large practical win whenever memory, not time, is the binding constraint.

Implementation

def iddfs(graph, start, target, max_depth=50):
    '''Iterative deepening DFS: run depth-limited DFS with an increasing depth
    cutoff (0, 1, 2, ...) until target is found or max_depth is exceeded.
    Cycle safety uses PATH membership (the current recursion stack), not a
    global visited set: a global visited set would permanently block a node
    the first time any branch reaches it, even if a different, still-within-
    budget path to the target goes through that same node later in the same
    pass. Returns (path, depth) or (None, None) if not found within max_depth.'''
    for depth_limit in range(max_depth + 1):
        path = [start]
        on_path = {start}
        result = _dls(graph, start, target, depth_limit, path, on_path)
        if result is not None:
            return result, depth_limit
    return None, None

def _dls(graph, node, target, depth_left, path, on_path):
    if node == target:
        return list(path)
    if depth_left <= 0:
        return None
    for nbr in graph.get(node, []):
        if nbr in on_path:
            continue  # avoid cycling back onto our own current path
        path.append(nbr)
        on_path.add(nbr)
        found = _dls(graph, nbr, target, depth_left - 1, path, on_path)
        if found is not None:
            return found
        path.pop()
        on_path.remove(nbr)
    return None

if __name__ == "__main__":
    # Graph WITH a cycle: 0->1->2->3->0, plus a separate branch 1->4->5 (target).
    graph = {0: [1], 1: [2, 4], 2: [3], 3: [0], 4: [5], 5: []}

    path, depth = iddfs(graph, start=0, target=5, max_depth=10)
    print("path to target 5:", path, "found at depth:", depth)
    print("shallowest depth is correct (0->1->4->5 = depth 3):", depth == 3)

    path2, depth2 = iddfs(graph, start=0, target=99, max_depth=6)
    print("unreachable target returns:", path2, depth2)

    path3, depth3 = iddfs(graph, start=2, target=2, max_depth=3)
    print("start==target path:", path3, "depth:", depth3)

    big_cycle = {i: [(i + 1) % 20] for i in range(20)}
    path4, depth4 = iddfs(big_cycle, start=0, target=15, max_depth=25)
    print("20-node ring, 0 to 15 (shortest forward hop count):", depth4, path4 == list(range(16)))

Output (actually executed with python3):

path to target 5: [0, 1, 4, 5] found at depth: 3
shallowest depth is correct (0->1->4->5 = depth 3): True
unreachable target returns: None None
start==target path: [2] depth: 0
20-node ring, 0 to 15 (shortest forward hop count): 15 True

Worked example

Picture a search tree with branching factor $b = 2$ and a solution at depth $d = 3$. IDDFS runs:

• Depth-limited search to depth 0: only the root, no solution, cheap.
• Depth-limited search to depth 1: re-visits the root, then its 2 children, no solution.
• Depth-limited search to depth 2: re-visits depths 0 and 1, then depth 2 (4 nodes), no solution.
• Depth-limited search to depth 3: re-visits depths 0 through 2, then finds the solution among the 8 nodes at depth 3.

Nodes visited across all passes: $1 + (1+2) + (1+2+4) + (1+2+4+8) = 1 + 3 + 7 + 15 = 26$, versus a single BFS pass visiting $1+2+4+8 = 15$ nodes to reach the same depth. The repeated work (26 versus 15) is real but bounded: it is dominated by the final pass's own $1+2+4+8=15$ nodes, so total work stays within a constant factor of a single BFS pass for a fixed branching factor, while memory at any moment never exceeds the current path length (3), not the frontier width (8).

Trade-offs and pitfalls

• When IDDFS is preferable to plain BFS or DFS: the search space is large or its shape (branching factor, depth) is not known ahead of time, a shallow solution is expected or specifically wanted, and memory, not time, is the binding constraint. This is the classic profile of planning and game-tree search under a memory budget.
• When it is not worth it: if the search space is small enough that BFS's memory cost is a non-issue, plain BFS is simpler and does strictly less total work.
• Relation to planning. In state-space planning where the "depth" is plan length, IDDFS corresponds to iterative deepening over plan length: try to find any 0-step plan, then any 1-step plan, and so on, which is exactly the shape needed when the shortest valid plan length is unknown in advance. Combined with a cost heuristic (an estimate of remaining distance to the goal) instead of a plain depth bound, this generalizes to IDA* (iterative-deepening A*), which iterates over an increasing cost threshold rather than a depth threshold.
• Common mistake: forgetting to guard against cycles WITHIN a single depth-limited pass on a graph (as opposed to a tree); without that, a cyclic graph can cause a single depth-limited pass to loop forever within its own depth budget. The guard should be PATH-based (track only the nodes on the current root-to-node branch, as the implementation above does with on_path), not a single global visited set for the whole pass: a global per-pass visited set would permanently block a node the first time ANY branch reaches it, which can wrongly rule out a different, still-within-budget path to the target that happens to pass through that same node later in the same depth-limited pass.
• Common mistake: treating IDDFS's total-work overhead as a memory cost; it is a TIME overhead (redoing shallow work on every pass), not additional memory.

Direct answer

Both breadth-first search (BFS) and depth-first search (DFS) run in $O(V+E)$ time on an adjacency list, because the total work is bounded by the number of vertices touched plus the total number of neighbor-pointer traversals across the whole run, which sums to exactly $E$ (or $2E$ for an undirected graph, still $O(E)$). On an adjacency matrix, both run in $O(V^2)$, because finding a vertex's neighbors means scanning its entire row of $V$ entries regardless of how many of them are actually edges, and this happens for every vertex.

Structured elaboration

Adjacency list derivation. Let $\text{visited}[]$ track which vertices have been processed, guaranteeing each vertex is expanded at most once.

• Per-vertex overhead: each of the $V$ vertices is enqueued/pushed and dequeued/popped at most once, each operation $O(1)$ amortized, contributing $\Theta(V)$ total.
• Per-edge overhead: when a vertex $u$ is processed, the algorithm iterates its adjacency list, one step per neighbor. Summed across every vertex processed during the traversal, this equals the total number of adjacency-list entries touched. For a directed graph, $\sum_v \deg^+(v) = E$ (every edge appears exactly once, in its source's list). For an undirected graph, $\sum_v \deg(v) = 2E$ (every edge appears once in each endpoint's list), still $\Theta(E)$ since the factor of 2 is a constant.
• Total: $\Theta(V) + \Theta(E) = \Theta(V+E)$.
• Why an edge is inspected only a constant number of times: visited[] ensures a vertex's adjacency list is scanned exactly once (when that vertex itself is dequeued/popped), not once per incoming edge; without this guard, a vertex reachable by many edges could have its list rescanned redundantly.

Adjacency matrix derivation.

• Per-vertex overhead: identical to the list case, $\Theta(V)$ for enqueue/dequeue bookkeeping.
• Per-edge overhead: finding vertex $u$'s neighbors means scanning row $u$ of the $V \times V$ matrix, $V$ cell checks, REGARDLESS of how many of those cells are actually 1 (an edge). This happens once per processed vertex, giving $V$ vertices $\times$ $V$ cells each $= \Theta(V^2)$.
• Total: $\Theta(V) + \Theta(V^2) = \Theta(V^2)$, dominated entirely by the per-vertex row scan; the matrix's time bound does not depend on $E$ at all, sparse or dense.

Directed versus undirected. The derivation's shape is identical for both; the only difference is the constant factor in the edge-count term ($E$ for directed, $2E$ for undirected in the list case; the matrix case is unaffected either way since a full row is scanned regardless of the graph's directedness, though an undirected adjacency matrix is symmetric, which some implementations exploit to only store, though not necessarily to only SCAN, roughly half the entries).

Assumptions about the visiting mechanism. This analysis assumes iterating a vertex's adjacency list (or a matrix row) costs $O(1)$ per element visited, true for a plain array, a linked list, or a language iterator with $O(1)$ amortized next(). If neighbors were instead stored in a structure with a more expensive per-element access cost (a balanced tree ordered by neighbor id, for instance, used to support fast edge-existence checks), the per-edge term would pick up an extra $O(\log \deg(v))$ factor, changing the bound to $O(V + E \log(\text{avg degree}))$; the classic $O(V+E)$ result specifically assumes the cheapest reasonable neighbor-storage structure, not any adjacency-list variant whatsoever.

Worked example

Take $V = 1000$, and consider two graphs on that vertex set: a sparse one with $E = 2000$ (average degree 4) and a dense one with $E = 400{,}000$ (close to the $V(V-1)/2 \approx 499{,}500$ maximum for an undirected simple graph).

Adjacency-list time is $\Theta(V+E)$: $1000 + 2000 = 3000$ "units" of work for the sparse graph, $1000 + 400{,}000 = 401{,}000$ units for the dense one, work that scales directly with how many real edges exist.

Adjacency-matrix time is $\Theta(V^2) = 1000^2 = 1{,}000{,}000$ units of work for BOTH graphs, since the matrix traversal cost never looks at $E$ at all. For the sparse graph, the matrix does roughly 333x MORE work than the list (1,000,000 vs 3,000); for the dense graph, the gap narrows sharply but does NOT invert: the list's 401,000 units is still fewer than the matrix's 1,000,000, about 2.5x less. This is not an artifact of the chosen numbers: for ANY simple graph (no self-loops or parallel edges), $E$ is bounded by $V(V-1)/2$, so $V+E$ is bounded by $V(V+1)/2 \approx V^2/2$, always roughly HALF of the matrix's $V^2$, even at the maximum possible density (at $V=1000$'s true max, $E=499{,}500$, list work is 500,500 versus the matrix's 1,000,000, still about 2x less). The list's raw operation count can never actually exceed the matrix's for a full traversal of a simple graph; there is no density at which this accounting makes the matrix outright faster. What DOES happen as $E$ approaches $V^2$ is that the list's ASYMPTOTIC advantage evaporates (both become $\Theta(V^2)$), which is why dense-graph implementations reach for the matrix anyway: not because it traverses faster, but because its better constant factors, contiguous memory with strong cache locality, a simpler implementation, and $O(1)$ point edge-existence checks the list cannot match, are worth more once the list's shrinking speed edge is no longer an order-of-magnitude win.

Trade-offs and pitfalls

• Common mistake: assuming the $O(V+E)$ vs $O(V^2)$ comparison means the list is dramatically faster at every density, OR (the opposite, equally wrong error) that a genuinely dense graph flips the ordering and makes the matrix faster in raw traversal work. Neither extreme is right: for a simple graph the list's operation count can never exceed roughly $V^2/2$, so it never actually loses this race, but its margin shrinks from over 300x at low density to under 3x near maximum density, which is why dense-graph code often reaches for the matrix anyway, not because it got faster, but because the list's shrinking advantage stops being worth its extra implementation complexity once cache locality and $O(1)$ edge lookups are on the table.
• Common mistake: treating $O(V+E)$ as automatically implying the algorithm is "linear." It is linear in the SIZE OF THE INPUT (which is itself $\Theta(V+E)$ for an adjacency list), not linear in $V$ alone; a graph where $E$ grows quadratically in $V$ makes the traversal quadratic too, list or no list.
• The visited-array guard is what makes the list bound tight, not incidental to it. Removing it (allowing a vertex's adjacency list to be rescanned every time any neighbor points to it) would make the bound $O(V \cdot E)$ in the worst case (a densely-interconnected graph revisiting the same expensive vertex repeatedly), which is exactly the kind of subtle omission that turns a correct asymptotic claim into a wrong one.
• Space follows the same split: adjacency list is $\Theta(V+E)$ (proportional to what actually exists), matrix is $\Theta(V^2)$ (fixed regardless of edge count), independent of the traversal algorithm's own $O(V)$ queue/stack overhead, which is the same for both representations.

Direct answer

Enumerate simple paths (no repeated vertex) up to $k$ edges using depth-first search (DFS) with backtracking: extend the current path by one unvisited neighbor at a time, record a match whenever the destination is reached, and undo the last step (backtrack) once a branch is exhausted or the length budget is used up. In production, this must ship with explicit safeguards, a cap on the number of returned paths and, ideally, a generator interface, since the number of simple paths can grow exponentially with $k$.

Structured elaboration

Why backtracking, not plain DFS. A plain DFS that only tracks a global visited set would incorrectly mark a node as permanently visited the first time any path reaches it, preventing that node from appearing in a DIFFERENT simple path later. Path enumeration needs "visited along the CURRENT path only," which is exactly what backtracking provides: add the node to the path (and a per-path visited set) on the way down, remove it again on the way back up, so the same node can legitimately appear in multiple distinct paths explored one after another.

Why the length cap matters structurally, not just as an optimization. Once the current path already has $k$ edges, no further extension can still be a valid answer, so the recursion should stop extending at that point regardless of whether the destination was reached, this prunes the search rather than merely limiting the OUTPUT after the fact.

Production safeguards. Two independent knobs matter: a max_paths cap on how many results are returned (protects the CALLER from an unbounded result set) and, in a fuller production version, a wall-clock or work-based timeout (protects the WORKER from spending unbounded time on a single request); yielding results incrementally via a generator lets a caller consume the first several paths without waiting for, or paying the memory cost of, an exhaustive enumeration.

Worked example

from typing import Dict, Iterable, List

def enumerate_simple_paths(adj: Dict[int, Iterable[int]], src: int, dst: int, k: int,
                            max_paths: int = None) -> List[List[int]]:
    '''DFS/backtracking enumeration of simple (no repeated node) paths from src to dst
    using at most k edges. max_paths caps output size for production safety.'''
    results: List[List[int]] = []

    def backtrack(node, path, path_set):
        if max_paths is not None and len(results) >= max_paths:
            return
        if node == dst:
            results.append(list(path))
            return
        if len(path) - 1 >= k:
            return
        for nbr in adj.get(node, ()):
            if nbr in path_set:
                continue
            path.append(nbr)
            path_set.add(nbr)
            backtrack(nbr, path, path_set)
            path.pop()
            path_set.discard(nbr)

    backtrack(src, [src], {src})
    return results

if __name__ == "__main__":
    # Diamond graph (two disjoint routes from 0 to 5) with an extra edge 4->0
    # that would create a cycle if the visited-per-path guard were missing.
    adj = {
        0: [1, 2],
        1: [3],
        2: [3],
        3: [4],
        4: [0, 5],
        5: [],
    }
    all_paths = enumerate_simple_paths(adj, 0, 5, k=10)
    print("All simple paths 0 -> 5 (k<=10):", all_paths)
    print("count:", len(all_paths))

    capped = enumerate_simple_paths(adj, 0, 5, k=3)
    print("Paths 0 -> 5 with at most 3 edges:", capped, "(expect none: shortest path needs 4 edges)")

    exactly4 = enumerate_simple_paths(adj, 0, 5, k=4)
    print("Paths 0 -> 5 with at most 4 edges:", exactly4)

    # max_paths safeguard against combinatorial blow-up
    fanout = {0: list(range(1, 21))}
    for i in range(1, 21):
        fanout[i] = [100]
    fanout[100] = []
    capped_count = enumerate_simple_paths(fanout, 0, 100, k=2, max_paths=5)
    print("Wide fan-out graph has 20 possible 2-edge paths; max_paths=5 caps output at:", len(capped_count))

Output (actually executed with python3):

All simple paths 0 -> 5 (k<=10): [[0, 1, 3, 4, 5], [0, 2, 3, 4, 5]]
count: 2
Paths 0 -> 5 with at most 3 edges: [] (expect none: shortest path needs 4 edges)
Paths 0 -> 5 with at most 4 edges: [[0, 1, 3, 4, 5], [0, 2, 3, 4, 5]]
Wide fan-out graph has 20 possible 2-edge paths; max_paths=5 caps output at: 5

Complexity

• Worst case time and space: $O(b^k)$ where $b$ is the branching factor, exponential in $k$, since the number of simple paths itself can be exponential in a densely connected graph.
• Memory for the active recursion: $O(k)$ per path in progress (the current path and its per-path visited set), independent of how many completed paths have been found so far, if results are streamed rather than accumulated.
• With max_paths set, the function still explores in the worst case some unbounded-looking branches before finding enough valid paths, worst-case time is not improved by the cap alone in an adversarial graph, only the OUTPUT size is bounded; a true worst-case time bound needs a separate node/step budget, not shown here.

Edge cases

• src == dst: the first check (node == dst) fires immediately, returning [[src]], a trivial zero-edge path.
• No path within $k$ edges: returns an empty list, demonstrated above with the k=3 case.
• Cycles in the input graph (the 4->0 edge above): handled safely, since path_set prevents revisiting any node already on the CURRENT path, so the cycle simply cannot be taken without repeating a node, which the simple-path definition already forbids.
• Very wide fan-out: demonstrated with the 20-branch example, max_paths caps the returned count without needing the caller to consume an unbounded generator.

Trade-offs and pitfalls

• Common mistake: using a single, path-independent visited set shared across the whole search instead of a per-path one; this would incorrectly prevent a node from ever being reused in a different candidate path, undercounting or completely missing valid simple paths that happen to share an intermediate node.
• For weighted graphs, replace the edge-count budget k with a cost budget, and prune whenever the accumulated path cost exceeds it, rather than counting edges; this changes the pruning condition but not the backtracking structure.
• Approximate path-counting (for example a random-walk-based Monte Carlo estimate, or dynamic-programming counts of paths WITHOUT materializing them, only valid when repeated vertices are allowed or the graph is a DAG so simple-path counting is tractable) is worth reaching for once exact enumeration itself, not just returning the results, becomes the bottleneck, for instance when the caller only needs "roughly how many paths exist," not the paths themselves.
• Parallelizing across workers: the search tree can be split at the first branching level (each worker owns one of src's neighbors as its subtree root) with max_paths tracked as either a shared, coordinated budget or an independent per-worker budget depending on whether a hard global cap or a best-effort cap is required.