DSA Depth-First Search

How it works

The implementation stores an iterator for each active branch and marks a vertex when that branch first enters it. It therefore handles shared descendants and cycles without repeatedly visiting their vertices. The listed neighbor order determines which branch is tried first. Depth-first order is not a shortest-hop guarantee, and visiting only from one start does not cover a disconnected graph’s other components automatically.

Run the code

Select Try in playground to load this complete source into the existing Python editor. It does not run automatically; choose Run when ready. These examples use only the Python standard library and small fictional inputs. They do not need database services, extra packages or personal files.

For local work, save the complete source as depth-first.py and run python depth-first.py. The local review uses Python 3.12.14; the browser uses the existing Pyodide 0.27.7 runtime. Keep inputs small, respect explicit table/tour budgets and account for recursion limits before increasing a fixture’s size.

Example

def validate_graph(graph, weighted=False, nonnegative=False):
    if not isinstance(graph, dict):
        raise ValueError("Expected an adjacency dictionary")
    if any(not isinstance(vertex, str) for vertex in graph):
        raise ValueError("String vertex labels required")
    for vertex, neighbors in graph.items():
        for edge in neighbors:
            if weighted:
                target, weight = edge
                if type(weight) is not int or (nonnegative and weight < 0):
                    raise ValueError("Invalid integer edge weight")
            else:
                target = edge
            if target not in graph:
                raise ValueError("Unknown target vertex")

def dfs(graph, start):
    validate_graph(graph)
    if start not in graph:
        raise ValueError("Unknown start vertex")
    seen, order = {start}, [start]
    pending = [iter(graph[start])]
    while pending:
        try:
            target = next(pending[-1])
        except StopIteration:
            pending.pop()
            continue
        if target not in seen:
            seen.add(target)
            order.append(target)
            pending.append(iter(graph[target]))
    return order

print(dfs({"gate": ["oak", "pond"], "oak": ["shed"], "pond": ["shed"], "shed": [], "hill": []}, "gate"))

Expected result

['gate', 'oak', 'shed', 'pond']

Gate follows oak to shed before returning for pond. The iterator stack preserves where each active branch paused, which is more precise than pushing every neighbor and confusing discovery with completed exploration. The graph’s unreachable hill remains outside this start’s traversal.

Time, space and assumptions

Validation and traversal take O(V+E) time for adjacency lists. The seen set, order and active iterator stack are O(V), avoiding Python recursion frames for this implementation.