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, …
CurrentVisited / acceptedUnvisited
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 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.#include <functional>
#include <vector>
std::vector<int> dfs(const std::vector<std::vector<int>>& adj,
int source) {
std::vector<bool> seen(adj.size(), false);
std::vector<int> order;
std::function<void(int)> visit = [&](int u) {
seen[u] = true;
order.push_back(u);
for (int v : adj[u]) {
if (!seen[v]) visit(v);
}
};
visit(source);
return order; // Only vertices reachable from source.
}