C++ graphs: BFS, DFS, and connected components

Store a graph as adjacency lists, visit it breadth-first and depth-first, and count its components.

C++

#include <iostream>
#include <queue>
#include <vector>

void dfs(const std::vector<std::vector<int>>& g, int node, std::vector<bool>& seen) {
  seen[node] = true;
  std::cout << " " << node;
  for (int next : g[node]) {
    if (!seen[next]) {
      dfs(g, next, seen);
    }
  }
}

int main() {
  std::vector<std::vector<int>> g(7);
  auto edge = [&](int a, int b) {
    g[a].push_back(b);
    g[b].push_back(a);
  };
  edge(0, 1); edge(0, 2); edge(1, 3); edge(2, 3); edge(4, 5);

  std::vector<bool> seen(7, false);
  std::queue<int> pending;
  pending.push(0);
  seen[0] = true;
  std::cout << "bfs from 0:";
  while (!pending.empty()) {
    int node = pending.front();
    pending.pop();
    std::cout << " " << node;
    for (int next : g[node]) {
      if (!seen[next]) {
        seen[next] = true;
        pending.push(next);
      }
    }
  }
  std::cout << "\n";

  std::vector<bool> visited(7, false);
  std::cout << "dfs from 0:";
  dfs(g, 0, visited);
  std::cout << "\n";

  std::vector<bool> marked(7, false);
  int components = 0;
  for (int start = 0; start < 7; ++start) {
    if (!marked[start]) {
      ++components;
      std::queue<int> q;
      q.push(start);
      marked[start] = true;
      while (!q.empty()) {
        int node = q.front();
        q.pop();
        for (int next : g[node]) {
          if (!marked[next]) {
            marked[next] = true;
            q.push(next);
          }
        }
      }
    }
  }
  std::cout << "components: " << components << "\n";
}

Output

bfs from 0: 0 1 2 3
dfs from 0: 0 1 3 2
components: 3

Explanation

A graph is a set of nodes joined by edges. An adjacency list stores, for every node, the list of its neighbours, which uses O(V + E) memory and is the usual choice for sparse graphs. Breadth-first search (BFS) visits nodes in layers using a queue, and finds shortest paths in unweighted graphs. Depth-first search (DFS) goes as deep as possible before backtracking, using recursion or an explicit stack.

Both searches keep a visited array so that no node is processed twice. Starting a new search from every node that has not been visited counts the connected components: groups of nodes that can reach each other. Each search takes O(V + E) time in total.

Explore the dry run

Guided walkthroughReady

1#include <iostream>

2#include <queue>

3#include <vector>

5void dfs(const std::vector<std::vector<int>>& g, int node, std::vector<bool>& seen) {

6 seen[node] = true;

7 std::cout << " " << node;

8 for (int next : g[node]) {

9 if (!seen[next]) {

10 dfs(g, next, seen);

11 }

12 }

13}

15int main() {

16 std::vector<std::vector<int>> g(7);

17 auto edge = [&](int a, int b) {

18 g[a].push_back(b);

19 g[b].push_back(a);

20 };

21 edge(0, 1); edge(0, 2); edge(1, 3); edge(2, 3); edge(4, 5);

23 std::vector<bool> seen(7, false);

24 std::queue<int> pending;

25 pending.push(0);

26 seen[0] = true;

27 std::cout << "bfs from 0:";

28 while (!pending.empty()) {

29 int node = pending.front();

30 pending.pop();

31 std::cout << " " << node;

32 for (int next : g[node]) {

33 if (!seen[next]) {

34 seen[next] = true;

35 pending.push(next);

36 }

37 }

38 }

39 std::cout << "\n";

41 std::vector<bool> visited(7, false);

42 std::cout << "dfs from 0:";

43 dfs(g, 0, visited);

44 std::cout << "\n";

46 std::vector<bool> marked(7, false);

47 int components = 0;

48 for (int start = 0; start < 7; ++start) {

49 if (!marked[start]) {

50 ++components;

51 std::queue<int> q;

52 q.push(start);

53 marked[start] = true;

54 while (!q.empty()) {

55 int node = q.front();

56 q.pop();

57 for (int next : g[node]) {

58 if (!marked[next]) {

59 marked[next] = true;

60 q.push(next);

61 }

62 }

63 }

64 }

65 }

66 std::cout << "components: " << components << "\n";

67}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
Two groups: the square 0-1-3-2, and the pair 4-5. Node 6 is alone.	`—`	—
BFS starts from node 0 with a queue.	`queue = [0]`	—
Mark a node when it is queued, so it is never queued twice.	`queue = [0]`	—
DFS follows the first neighbour as deep as possible: 0, 1, 3, then back to 0's other neighbour 2.	`queue = [0]`	bfs from 0: 0 1 2 3 dfs from 0: 0 1 3 2
Each unmarked start node begins a new component.	`queue = [0]`	bfs from 0: 0 1 2 3 dfs from 0: 0 1 3 2
The components are {0,1,2,3}, {4,5}, and the isolated node {6}.	`queue = [0]`	bfs from 0: 0 1 2 3 dfs from 0: 0 1 3 2 components: 3

Cost and common mistakes

BFS, DFS, and the component count are O(V + E).

Without a visited array a graph with a cycle makes the search run forever.
Recursive DFS can overflow the stack on a long path. Use an explicit stack for large graphs.
BFS gives shortest paths only when all edges have the same cost. Use Dijkstra's algorithm for weighted edges.

Try it yourself

How many components does the graph have?

Reveal answer and reasoning

Three: nodes 0, 1, 2, 3 form one component, 4 and 5 form another, and node 6 is alone in the third.

C++ graphs: BFS, DFS, and connected components

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading