C++UCS301
Graphs & ApplicationsC++17

Depth-First Search

DFS follows one path deeply before backtracking and supports cycle detection, ordering, components, and structural analysis.

Open this in the visual lab

What to understand

  • Recursion and explicit stacks
  • Entry/exit states
  • Cycle detection
  • Topological intuition

Remember this

  1. 1Recursive DFS uses the call stack
  2. 2Track parent in undirected cycle detection
  3. 3Colour states help directed graphs

Detailed notes

DFS explores one unvisited neighbour chain until it cannot continue, then backtracks. Entry and exit times expose nesting relationships that power cycle tests, topological ordering, and component algorithms.

Recursive DFS is concise but its call stack may reach V on a path-shaped graph. An explicit stack avoids process-stack overflow and can record the same traversal state.

How it works

  1. 1Mark a vertex before exploring its neighbours.
  2. 2Recursively or iteratively visit each unvisited neighbour.
  3. 3Track parent for undirected cycle detection.
  4. 4Use white, grey, and black states for directed cycles.

Worked trace

Depth-first traversal from A

Alphabetical neighbours on the same six-node graph
  1. 1Visit A and descend to B.
  2. 2From B descend to D; D has no new neighbour, so backtrack.
  3. 3From B continue to E, then F, then C.
  4. 4Backtrack until the stack is empty.
Result: One possible order: A,B,D,E,F,C

Where it is used

  • Reachability and connected components
  • Cycle detection and topological ordering
  • Maze search and backtracking

Common mistakes

  • Treating the parent edge as an undirected cycle
  • Recursing too deeply on large graphs
  • Assuming one DFS call covers a disconnected graph

Complexity analysis

OperationBestAverageWorstExtra space
TraversalO(V+E)O(V+E)O(V+E)O(V)

C++ implementation

C++17 reference
main.cpp

Recursive DFS

Run this from every still-unvisited vertex to traverse a disconnected graph.

void dfs(int current, const vector<vector<int>>& graph,
         vector<bool>& visited) {
    visited[current] = true;
    cout << current << ' ';
    for (int next : graph[current])
        if (!visited[next]) dfs(next, graph, visited);
}

vector<bool> visited(graph.size(), false);
for (int vertex = 0; vertex < graph.size(); ++vertex)
    if (!visited[vertex]) dfs(vertex, graph, visited);
11 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.