Visualizer CodeViz · Algorithms, visualized

Part II · Undirected graphs · week 1

Depth-first search

Mark a vertex, then recur into any unmarked neighbour. One call per vertex, two looks per edge — and the recursion stack is the path you took to get here.

Run the animation, step by step → generated live from any input you type — nothing is pre-recorded

Cost and properties

timeO(V + E)
spaceO(V)
findsconnectivity, paths, cycles, bridges
path foundnot the shortest

Reference: Sedgewick & Wayne, §4.1; Trémaux 1882.

Depth-first search in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

class DepthFirstPaths:
    # Marks every vertex reachable from s, and records the edge that first
    # reached each one -- edge_to[] is a TREE rooted at s.

    def __init__(self, graph, s):
        self.marked = [False] * graph.V
        self.edge_to = [None] * graph.V
        self.s = s
        self._dfs(graph, s)

    def _dfs(self, graph, v):
        self.marked[v] = True             # visit v
        for w in graph.adj(v):
            if not self.marked[w]:        # every edge is looked at twice
                self.edge_to[w] = v       # remember how we reached w
                self._dfs(graph, w)       # ... and go deeper immediately

    def has_path_to(self, v):
        return self.marked[v]

    def path_to(self, v):                 # walk edge_to back to the source
        if not self.marked[v]:
            return None
        path, x = [], v
        while x != self.s:
            path.append(x)
            x = self.edge_to[x]
        path.append(self.s)
        return list(reversed(path))

Why it works

The whole algorithm in two lines

Mark v. For each unmarked neighbour w, record how you got there and recur. The marked[] array is what stops the recursion looping forever, and edge_to[] quietly builds a spanning tree of everything reachable from s: follow it backwards from any vertex and you have a path to the source.

Why it is linear

_dfs runs at most once per vertex (the mark guarantees that), and inside it every entry of every adjacency list is examined once. Each undirected edge appears in two lists, so it is looked at twice: total work O(V + E). Note that is V plus E, not V times E — the adjacency-list representation is what makes it so.

What the recursion stack means

The stack holds exactly the vertices on the current path from s. That is why DFS is the natural tool for questions about paths and structure: cycle detection (an edge back to a vertex still on the stack), bridges and articulation points, planarity, and Euler tours. It is also the classic maze-solving rule — Trémaux's, from 1882, string and all.

What it is not

DFS paths are not shortest. Run the a cycle preset: reaching vertex 5 from 0 takes the long way round. If you want shortest paths in an unweighted graph, the only change needed is to replace the recursion with a queue — that is BFS.

DFS also recurses as deep as the longest path, so on a large graph the real implementation must use an explicit stack or it will overflow.

What to try in the animation

Undirected edges v-w. Adjacency lists are visited in ascending order, so the traversal is reproducible.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

Open Depth-first search in the player →

The rest of Undirected graphs