Graph Traversal -- DFS, BFS, and BFS From Both Sides

Posted on   |   In   |  

The key point of DFS is keep tracking all visited nodes and make sure check the end condition correctly. Usually the end condition is reaching certain length or certain node.

The key point of BFS is also keep tracking visited nodes. Unlike DFS which uses recursion, BFS uses a queue to do layer-by-layer traversal.

In this implementation, we do not keep the lavel, or depth, of the nodes we visited, a simple way to do that is insert an indicator to indicate the end of a layer:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
deque<Node*> frontier;
vector<int> visited(GRAPH_SIZE, false);
frontier.push_back(startNode);
visited[startNode->label] = true;
int level = 0; // start node is at level 0
while(frontier.size() > 0) {
  // push a nullptr into the queue as a label, all nodes before that belongs to the same level
  frontier.push_back(nullptr);
  while(frontier.front() != nullptr) {
    /*Do normal works, push_back a new neighbor that we did not visited*/
    frontier.pop_back(); // remove current node
  }
  frontier.pop_back(nullptr); // now we reach the end of the level, add level by 1
  ++level;
}

Breath First Search with Two Frontiers

The following code is for the Word Ladder problem. I used BFS with two frontiers to solve this problem. The details can be seen in the code comment