Workspace

Problem workspace

3 day streakD

Depth-First Search (DFS)

EasyGraphsTraversal

The challenge

Visit every vertex reachable from a source. Explore as far as possible along one branch before backtracking, and return the discovery order.

Works on directed and undirected graphs. Mark vertices before recursing to avoid cycles.

Example

From A: A → B → C → F → D → E. This is one valid DFS order; neighbor order determines the result.

Use the walkthrough below to inspect the input and each state change.

See DFS, step by step

Follow the edges. Watch the state change.

Undirected · 6 vertices · 6 edgesA = 0, B = 1, …
Connected graphUndirected graph with 6 vertices. Start at A. Mark a vertex when entering it. Follow neighbors in the order shown in the edge list. The edge list and state table below provide the graph in text.ABCDEF
CurrentVisited / acceptedUnvisited
DFS depth (not shortest distance)
ABCDEF
0∞∞∞∞∞
Step 01 / 14

Start at A.

Mark a vertex when entering it. Follow neighbors in the order shown in the edge list.

dfs(A)

Recursion stack · top last

A
View input edges

A — B · A — F · B — C · C — F · C — D · D — E

Source: A. Adjacency entries follow this edge order.

Put it into code

The recursion stack remembers where to return after a branch finishes.

Vertices are numbered 0 to V − 1. C++ uses C++17 or later.

def dfs(adj, source):
    # adj[u] lists neighbors; source must be a valid vertex.
    seen = [False] * len(adj)
    order = []

    def visit(u):
        seen[u] = True
        order.append(u)
        for v in adj[u]:
            if not seen[v]:
                visit(v)

    visit(source)
    return order  # Only the source's reachable component.

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap