15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Depth first search (DFS) takes one unvisited neighbor and recurses as far as it can, then backs up when a vertex has no unvisited neighbor. It marks each vertex visited on entry, so no vertex is entered twice. It runs in O(V + E) time and uses O(V) auxiliary space.
| Data structure | Visited set plus the recursive call stack (LIFO) |
|---|---|
| Time | O(V + E) |
| Auxiliary space | O(V); a path graph keeps V active calls |
| Example from A | Discovery order A, B, D, C |
| Reaches | Only vertices reachable from the start |
Depth-first search (DFS) traverses a graph by taking one unvisited neighbor, exploring as far as it can through recursive calls, and then returning when it reaches a vertex with no unvisited neighbor.
You should already be able to:
The active recursive DFS calls form a call stack. Entering a recursive call adds one active frame; returning removes it.
Use these input rules:
adjacencyList maps each vertex to its neighbors in the stated order.start must be a vertex in adjacencyList.start.adjacencyList.For scope and background, see Undirected Graphs and this BFS and DFS lecture.
Use this adjacency list:
1A: [B, C]
2B: [A, D]
3C: [A, D]
4D: [B, C]Start DFS at A.
Keep four pieces of state separate:
| State | Meaning | Initial value |
|---|---|---|
| Adjacency list | The graph and its neighbor order | As shown above |
visited | Vertices entered by DFS | {} |
order | Discovery order | [] |
| Call stack | Active recursive DFS calls | [] |
The neighbor order is part of the input. From A, DFS sees B before C. From B, it sees A before D.
Start by calling DFS(A).
DFS from A: A, B, D, C are entered in turn so the call stack grows to [A, B, D, C]. C finds nothing new, so calls return C, D, B, A. Order is [A, B, D, C].
| State | Action | visited | order | Call stack |
|---|---|---|---|---|
| 0 | Enter DFS(A). Mark A; append it. | {A} | [A] | [A] |
| 1 | From A, inspect B. It is unvisited, so enter DFS(B). | {A, B} | [A, B] | [A, B] |
| 2 | From B, inspect A. It is visited, so skip it. Then inspect D; enter DFS(D). | {A, B, D} | [A, B, D] | [A, B, D] |
| 3 | From D, inspect B. It is visited, so skip it. Then inspect C; enter DFS(C). | {A, B, D, C} | [A, B, D, C] | [A, B, D, C] |
| 4 | From C, inspect A and D. Both are visited. Return from C, then D, then B, then A. | {A, B, D, C} | [A, B, D, C] | [] |
| 5 | All calls have returned. | {A, B, D, C} | [A, B, D, C] | [] |
At C, DFS finds no unvisited neighbor. C remains in visited, and the call returns to D.
After DFS(C) returns, D has no more neighbors to inspect, so DFS(D) returns. The same sequence occurs for B and then A.
Every vertex on the call stack has already been marked visited:
1[A] A is visited
2[A, B] A and B are visited
3[A, B, D] A, B, and D are visited
4[A, B, D, C] all four are visitedOnce a vertex appears in visited, it remains there. No later recursive call can enter that vertex again.
The required loop-and-recursion invariant is:
Every vertex currently on the DFS call stack is visited, and all vertices discovered before a recursive call remain visited throughout that call. A vertex is recursively entered at most once.
Marking happens before scanning neighbors. In an undirected edge such as A—B, the list for B can point back to A. Since A is already marked, B skips it instead of calling DFS(A) again.
The discovery order records the same event as marking: first entry into a vertex.
Begin with an empty visited structure and empty discovery order.
For the current vertex:
For the example, this produces the chain:
1DFS(A)
2 DFS(B)
3 DFS(D)
4 DFS(C)The return path is the reverse:
1return C
2return D
3return B
4return AThe algorithm explores only the connected portion reachable from the start vertex. If a graph contains an isolated vertex that cannot be reached from start, DFS does not include it.
11 function dfsOrder(adjacencyList, start) -> list of Vertex
22 # Input:
33 # adjacencyList: map from each vertex to an ordered list of neighbors
44 # start: vertex at which traversal begins
55 # Return:
66 # discovery order of vertices reachable from start
77 # Mutation:
88 # does not mutate adjacencyList
99
1010 if start is not a key in adjacencyList
1111 raise ValidationError("start must be a vertex in adjacencyList")
1212
1313 visited <- empty set
1414 order <- empty list
1515
1616 visit(start, adjacencyList, visited, order)
1717 return order
1818
1919 function visit(vertex, adjacencyList, visited, order) -> nothing
2020 # Helper contract:
2121 # Preconditions:
2222 # - vertex is a key in adjacencyList
2323 # - vertex is not in visited
2424 # - visited and order are mutable shared traversal state
2525 # Postcondition:
2626 # - every vertex reachable from vertex through vertices not previously
2727 # visited has been visited and appended once, respecting neighbor order
2828
2929 add vertex to visited
3030 append vertex to order
3131
3232 for each neighbor in adjacencyList[vertex], from first to last
3333 if neighbor is not in visited
3434 visit(neighbor, adjacencyList, visited, order)
3535
3636 returnThe helper mutates visited and order. It does not return a separate traversal list. All recursive calls contribute to the same discovery order.
Use the original input:
1A: [B, C]
2B: [A, D]
3C: [A, D]
4D: [B, C]
5start = A| Step | Executed line | Resulting action and state |
|---|---|---|
| 1 | 10 | A is a key in adjacencyList, so validation succeeds. |
| 2 | 13–14 | visited = {} and order = []. |
| 3 | 16 | Call visit(A, adjacencyList, visited, order). |
| 4 | 29–30 | Add A; append A. visited = {A}, order = [A]. |
| 5 | 32 | Begin A’s neighbors in order: B, then C. |
| 6 | 33–34 | B is unvisited. Call visit(B, ...). |
| 7 | 29–30 | Add B; append B. visited = {A, B}, order = [A, B]. |
| 8 | 32 | Begin B’s neighbors in order: A, then D. |
| 9 | 33 | A is visited. Do not call visit(A). |
| 10 | 33–34 | D is unvisited. Call visit(D, ...). |
| 11 | 29–30 | Add D; append D. visited = {A, B, D}, order = [A, B, D]. |
| 12 | 32 | Begin D’s neighbors in order: B, then C. |
| 13 | 33 | B is visited. Do not recurse. |
| 14 | 33–34 | C is unvisited. Call visit(C, ...). |
| 15 | 29–30 | Add C; append C. visited = {A, B, D, C}, order = [A, B, D, C]. |
| 16 | 32 | Begin C’s neighbors in order: A, then D. |
| 17 | 33 | A is visited. Do not recurse. |
| 18 | 33 | D is visited. Do not recurse. |
| 19 | 36 | visit(C) returns to the call for D. |
| 20 | 36 | D has no remaining neighbors. visit(D) returns to B. |
| 21 | 36 | B has no remaining neighbors. visit(B) returns to A. |
| 22 | 32–33 | Continue A’s loop. Its next neighbor is C, which is now visited. Do not recurse. |
| 23 | 36 | A has no remaining neighbors. visit(A) returns. |
| 24 | 17 | Return order: [A, B, D, C]. |
The final discovery order is:
1[A, B, D, C]We show that dfsOrder returns each reachable vertex exactly once, in the discovery order determined by the supplied neighbor lists.
Before line 16, visited and order are empty.
When visit(start, ...) begins, lines 29 and 30 mark start and append it exactly once. The initial active call therefore has a visited vertex on the call stack, and the discovery order contains the first-entered vertex.
Consider an active call visit(vertex, ...).
vertex before its neighbors are inspected.vertex at that same first-entry moment.Every active call is for a visited vertex. Vertices discovered earlier remain in visited while deeper calls run. Because recursive calls occur only for unvisited vertices, no vertex is recursively entered twice.
A call returns only after its loop has inspected all neighbors. When a deeper call returns, the current call resumes its neighbor loop.
The graph has finitely many vertices. Each recursive entry adds a previously unvisited vertex to visited, and no vertex can be entered twice. Only finitely many calls occur. Every call eventually finishes scanning its finite neighbor list and returns.
When the initial call returns, every neighbor path reachable from start has been considered. Each reachable vertex was appended when first entered, and no vertex was appended twice. The returned list is exactly the DFS discovery order for the reachable vertices.
First count the work shown by the pseudocode.
V.So the work is:
1vertex initialization: O(V)
2adjacency-list scans: O(E)
3total time: O(V + E)The bound applies to an adjacency-list graph.
For auxiliary space:
visited can hold up to V vertices.A-B-C-D, recursive DFS can have one active call per vertex. The call stack can therefore contain V frames.1visited structure: O(V)
2recursion call stack: O(V)
3auxiliary space: O(V)The graph itself is excluded from auxiliary space. The returned order list is output storage.
Incorrect assumption: Recurse first, then mark the current vertex.
1for each neighbor in adjacencyList[vertex]
2 if neighbor is not in visited
3 visit(neighbor, ...)
4add vertex to visitedSmallest exposing input:
1A: [B]
2B: [A]Starting at A:
1visit(A) -> visit(B) -> visit(A) -> visit(B) -> ...Neither vertex is marked before the other call sees it.
Wrong result: Unbounded mutual calls.
Correction: Mark the current vertex at the start of its call, before scanning neighbors.
1add vertex to visited
2append vertex to orderIncorrect line:
1visit(neighbor, adjacencyList, visited, order)The recursive call happens even when neighbor is already visited.
Smallest exposing input:
1A: [B, C]
2B: [A, C]
3C: [B, A]The graph is the cycle A-B-C-A.
Wrong state: Calls revisit vertices around the cycle, causing repeated visits or nontermination.
Correction: Recurse only under the unvisited test.
1if neighbor is not in visited
2 visit(neighbor, adjacencyList, visited, order)Incorrect behavior: End the current call immediately after one recursive call returns.
Smallest exposing input:
1A: [B, C]
2B: []
3C: []Starting at A, the incorrect traversal enters B, returns, and then returns from A without inspecting C.
Wrong output:
1[A, B]Correction: Keep scanning the entire neighbor list after each recursive call returns. The correct output is:
1[A, B, C]Incorrect expectation: DFS from A should always list all immediate neighbors before deeper vertices.
Exposing input:
1A: [B, C]
2B: [D]
3C: []
4D: []A breadth-first order would be:
1[A, B, C, D]Recursive DFS follows B before returning to inspect C.
Correct DFS output:
1[A, B, D, C]Nested recursive calls and backtracking produce the difference.
| Input | Start | Expected behavior |
|---|---|---|
A: [] | A | Return [A]. One call marks A, finds no neighbors, and returns. |
Path A-B-C-D | A | Reach all vertices. The maximum active recursion depth is 4. |
Cycle A-B-C-A | A | Terminate because visited vertices are skipped. |
A: [B], B: [A], C: [] | A | Return [A, B]. C remains unvisited because it is unreachable from A. |
Empty graph {} | no valid start | Raise the documented validation failure. Do not attempt visit. |
Implement:
1dfsOrder(adjacencyList, start)using recursive DFS.
The executable tests verify this contract:
start is returned exactly once.1def dfs_order(adj, start):
2 if start not in adj:
3 raise ValueError("start must be a vertex")
4 visited = set()
5 order = []
6 visit(start, adj, visited, order)
7 return order
8
9def visit(vertex, adj, visited, order):
10 visited.add(vertex) # mark on entry, before scanning neighbors
11 order.append(vertex)
12 for neighbor in adj[vertex]:
13 if neighbor not in visited:
14 visit(neighbor, adj, visited, order)
15
16adj = {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"], "D": ["B", "C"]}
17print("order:", " ".join(dfs_order(adj, "A")))1import java.util.*;
2
3public class Main {
4 static List<String> dfsOrder(Map<String, List<String>> adj, String start) {
5 if (!adj.containsKey(start)) throw new IllegalArgumentException("start must be a vertex");
6 Set<String> visited = new HashSet<>();
7 List<String> order = new ArrayList<>();
8 visit(start, adj, visited, order);
9 return order;
10 }
11
12 static void visit(String vertex, Map<String, List<String>> adj, Set<String> visited, List<String> order) {
13 visited.add(vertex); // mark on entry, before scanning neighbors
14 order.add(vertex);
15 for (String neighbor : adj.get(vertex)) {
16 if (!visited.contains(neighbor)) {
17 visit(neighbor, adj, visited, order);
18 }
19 }
20 }
21
22 public static void main(String[] args) {
23 Map<String, List<String>> adj = new HashMap<>();
24 adj.put("A", List.of("B", "C"));
25 adj.put("B", List.of("A", "D"));
26 adj.put("C", List.of("A", "D"));
27 adj.put("D", List.of("B", "C"));
28 System.out.println("order: " + String.join(" ", dfsOrder(adj, "A")));
29 }
30}1#include <iostream>
2#include <map>
3#include <set>
4#include <stdexcept>
5#include <string>
6#include <vector>
7using namespace std;
8
9void visit(const string& vertex, map<string, vector<string>>& adj, set<string>& visited,
10 vector<string>& order) {
11 visited.insert(vertex); // mark on entry, before scanning neighbors
12 order.push_back(vertex);
13 for (const string& neighbor : adj[vertex]) {
14 if (!visited.count(neighbor)) {
15 visit(neighbor, adj, visited, order);
16 }
17 }
18}
19
20vector<string> dfsOrder(map<string, vector<string>>& adj, const string& start) {
21 if (!adj.count(start)) throw invalid_argument("start must be a vertex");
22 set<string> visited;
23 vector<string> order;
24 visit(start, adj, visited, order);
25 return order;
26}
27
28int main() {
29 map<string, vector<string>> adj = {
30 {"A", {"B", "C"}}, {"B", {"A", "D"}}, {"C", {"A", "D"}}, {"D", {"B", "C"}}};
31 cout << "order:";
32 for (const string& v : dfsOrder(adj, "A")) cout << " " << v;
33 cout << endl;
34}1function dfsOrder(adj, start) {
2 if (!adj.has(start)) throw new Error('start must be a vertex');
3 const visited = new Set();
4 const order = [];
5 visit(start, adj, visited, order);
6 return order;
7}
8
9function visit(vertex, adj, visited, order) {
10 visited.add(vertex); // mark on entry, before scanning neighbors
11 order.push(vertex);
12 for (const neighbor of adj.get(vertex)) {
13 if (!visited.has(neighbor)) {
14 visit(neighbor, adj, visited, order);
15 }
16 }
17}
18
19const adj = new Map([
20 ['A', ['B', 'C']],
21 ['B', ['A', 'D']],
22 ['C', ['A', 'D']],
23 ['D', ['B', 'C']],
24]);
25console.log(`order: ${dfsOrder(adj, 'A').join(' ')}`);LIFO. The active recursive calls form a call stack, and the most recent call finishes first. BFS is the FIFO one.
It visits everything reachable from a start vertex, which is what counting connected components needs. Cycle detection and topological sort are other standard uses.
On A: [B, C], B: [D], C: [], D: [], DFS gives A, B, D, C because it follows B before returning to C. BFS gives A, B, C, D.
Without that, A: [B], B: [A] recurses forever: visit(A) calls visit(B), which calls visit(A) again. Mark on entry and the second call is skipped.
Up to V active calls. On the path A-B-C-D, four calls are active at once. For very long paths, replace the call stack with an explicit stack.