Graph Traversal

The idea is pretty similar to tree traversal, except that we have to keep track of visited nodes to avoid infinite loops since graphs can have cycles.

Table of contents

1. Depth-First
2. Breadth-First

---

Depth-First

flowchart LR
  0((0)) --> 3((3))
  0 --> 1((1))
  2((2)) --> 0
  2 --> 3
  3 --> 4((4))
  1 --> 2

Assuming the adjacency list representation puts the neighbors in ascending order, the traversal path in the above graph is 0 1 2 3 4.

If it happens to be in descending order, the path would be 0 3 4 2 1.

void DepthFirst(const vector<vector<int>>& edges, vector<int>& res) {
  int n = static_cast<int>(edges.size());
  vector<bool> visited(n, false);
  return DepthFirstHelper(edges, 0, visited, res);
}

void DepthFirstHelper(const vector<vector<int>>& edges, int node,
                      vector<bool>& visited, vector<int>& res) {
  visited[node] = true;
  res.push_back(node);
  for (int neighbor : edges[node]) {
    if (!visited[neighbor]) {
      DepthFirstHelper(edges, neighbor, visited, res);
    }
  }
}

---

Breadth-First

flowchart LR
  0((0)) --> 3((3))
  0 --> 1((1))
  2((2)) --> 0
  2 --> 3
  3 --> 4((4))
  1 --> 2

The traversal path in the above graph would be 0 1 3 2 4.

As usual, Breadth-First approach uses a queue.

void BreadthFirst(const vector<vector<int>>& edges, vector<int>& res) {
  int n = static_cast<int>(edges.size());
  vector<bool> visited(n, false);
  queue<int> q;
  q.push(0);

  int node;
  while (!q.empty()) {
    node = q.front();
    q.pop();

    if (visited[node]) continue;
    visited[node] = true;
    res.push_back(node);

    for (int neighbor : edges[node]) {
      if (!visited[neighbor]) {
        q.push(neighbor);
      }
    }
  }
}

If you mark nodes visited while pushing them into the queue, you can skip the additional visited check after dequeue. Some people prefer this version because it’s more efficient (no duplicates in the queue).

However, I prefer this version because it seems more natural that you mark a node when you actually process it.