[Algo] Graph Traversal

DFS Traversal

Basic structure

• Greedily visit all the child nodes of a child node before going to the next child node.
• Use a vis vector to record all visited nodes.

void DFS(int cur ...) {
  if (vis[cur]) return;

  // visit all child nodes
  for (auto next:graph[cur]) {
    DFS(next ...);
  }
}

for (int i=0;i<n;++i) {
  DFS(i ...);
}

Ordering in DFS

• During the DFS traversal, we can give a timestamp to each node and order them.
• Preorder timestamp
  • Finding cut-vertex and cut-edge in Undirected Graph. In the DFS search tree, a smaller timestamp node can always to a large timestamp node following the traverse path. If we find a node, without backtracking the traverse path, cannot go to a smaller timestamp node, it means that the node’s subtree cannot go to any ancestor of the node. Therefore, removing this node, or removing the last edge of the traverse path, will disconnect the node’s subtree and the node’s ancestors.
• Postorder timestamp
  • Topological sorting in Directed Graph. During the traversal, if there is no loop, then the reverse of postorder sorting is a topological sorting. This is because in post ordering, we always visit all children nodes first, then the root node. Therefore, its reverse will always visit root node first before child nodes.

void DFS(int cur ...) {
  if (vis[cur]) return;

  // visit current node
  preorder_timestamp[cur] = cur_time;
  preorder_nodes.push_back(cur);
  preorder_cur_time++;

  // visit all child nodes
  for (auto next:graph[cur]) {
    DFS(next ...);
  }

  // backtrack to current node
  postorder_timestamp[cur] = cur_time;
  postorder_nodes.push_back(cur);
  postorder_cur_time++;
}

Coloring in DFS traversal

• We can color visited node differently during the traversal.
• Checking bipartite graph: we can alter the color of node during the traversal. If we find two adjacent nodes have same color, we return fasle.
• Checking loop in directed graph: In directed graph, only when a node connect to the current traverse path, it will be considered a loop. The color of node can be used to distinguish, if a node is in the current traverse path, or a previously already back-tracked traverse path.

void DFS(int cur ...) {
  if (color[cur]==1 || color[cur]==2) return;

  // visit current node
  color[cur] = 1;

  // visit all child nodes
  for (auto next:graph[cur]) {
    DFS(next ...);
  }

  // back track to current node
  color[cur] = 2;
}

DP in DFS traversal

• DFS implies a search tree. If there is no loop, we can conduct a dp algorithm based on the search tree structure.

void DFS(int cur ...) {
  if (vis[cur]) return;
  
  for (auto next:graph[cur]) {
    DFS(next ...);
  }

  // Aggregates all children dp value to current dp value
  dp[cur] = aggregate(dp[next1], dp[next2] ...);
}

BFS Traversal

• BFS can traverse nodes by one layer after another layer
• Coloring in BFS: we can alternatively color nodes in different layer differently. By this, we can check if the graph is bipartite.
• State in BFS: by maintaining a visited vector, we can find loop in an undirected graph.
• Ordering in BFS: removing zero in-degree nodes one by one, we can find the topological sorted order.
• DP in BFS: following the topological sorted order, we can calculate a successor’s DP value based on all its ancestors’ DP value.

while (!q.empty()) {
  int sz=q.size();
  for (int i=0;i<sz;++i) {
    // visit current node
    int cur = q.front(); q.pop();
    vis[cur] = true;

    // add successor nodes
    for (auto next:graph[cur]) {
      if (vis[next]) continue;
      q.push(next);
    }
  }
}