DFS

Time complexity: O(V+E)

Space complexity: O(V)

Data type: Graphs, Trees

Visualization

React Flow
Click any two vertices to connect them
Shift+click on the node to set it as "start"

Definition

Depth-First Search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (or any arbitrary node in case of a graph) and explores as far as possible along each branch before backtracking.

Constraints

  • Graph can be directed or undirected
  • May need cycle detection for certain applications
  • For disconnected graphs, needs to be run on each component

Step-by-step explanation

Arguments:

  • Graph representation - graph
  • Starting node - start
  • Visited set (optional) - visited

Explanation:

  • Mark the current node as visited
  • Process the current node (print, store, etc.)
  • For each adjacent node of the current node:
    • If the node hasn't been visited, recursively perform DFS on it
  • The algorithm explores as deep as possible before backtracking

Returns:

Depends on implementation - can return traversal order, connected components, or other graph properties

Example

1
#include <iostream>
2
#include <vector>
3
#include <stack>
4


5
void dfs(int start, const std::vector<std::vector<int>>& adj, std::vector<bool>& visited) {
6
    std::stack<int> s;
7
    s.push(start);
8


9
    while (!s.empty()) {
10
        int u = s.top();
11
        s.pop();
12


13
        if (!visited[u]) {
14
            visited[u] = true;
15
            std::cout << u << " ";
16


17
            // Dodajemy sąsiadów w odwrotnej kolejności, aby zachować zgodność z DFS rekurencyjnym
18
            for (auto it = adj[u].rbegin(); it != adj[u].rend(); ++it) {
19
                if (!visited[*it]) {
20
                    s.push(*it);
21
                }
22
            }
23
        }
24
    }
25
}