Breadth First Search and Single Source Shortest Path

mgcadmin 15-09-2021

A look at the breadth first search algorithm, and its application in graphs for finding single source shortest paths.

What is Breadth First Search?

Breadth First Search (BFS) is a method for searching tree and graph structures. It is also a traversal for technique for these two important abstract data types.  BFS employs the opposite strategy from Depth First Search(DFS): where DFS will search down one branch as far is it can go before turning around and heading down another branch, BFS will check the first node of every branch in a "level", before dropping down and searching the next level. This is why we can guarantee BFSs "completeness". It's also why in a tree, BFS is sometimes referred to a "level order" traversal. BFS has been likened to a ring of fire burning equally outwards in all directions from the starting point. Its search pattern can also be thought of the as the concentric ripples spreading outward created by dropping a pebble in a pond.

Order Matters

When searching a collection, any collection, be it an array, tree, graph, or some other data structure, the ordering that the elements are arranged in and the order in which the elements are accessed are of critical importance. For example, if you're searching for a specific value in an array of integers then the Binary Search algorithm can be used to drastically cut  down on the number of comparisons required for a search compared to the sequential search method - but only if the items are arranged in a sorted order. Like wise, if we're looking for a value in an implicitly infinite tree or graph, searching depth first may get lost exploring a branch leading AWAY from the vertex we're looking for, and thus never find the target we're searching for. Breadth First Search on the other hand suffers from no such drawback.

 

The Algorithm

Due to the nature of the Breadth First Search algorithm, while in the process of searching an unweighted graph it will also find the shortest path to whatever vertex it is we are looking for. The order which vertexes are accessed in BFS also means that it does NOT lend itself to a recursive implementation. There is a very simple queue based iterative form however. Where DFS utilizes a LIFO stack, BFS takes advantage of a FIFO queue. 

Lets take a look at a pseudo code description for Breadth First Search before getting into the implementation details in C++.

Procedure: BreadthFirstSearch <- Graph, starting Vertex, finishing Vertex
Let Q := a first in first out queue 
Let success := bool <- false
add starting to Q
mark starting as seen
camefrom <- starting := starting
while Q is not empty
   let current := first item in Q
   if current is target
      success := true

   for each child of current
    if seen child is false
    add child to Q
    seen child := true
end while
return success
end procedure

Breadth First Search in C++

Were going to be using the adjacency representation of a graph shown in my article Representing Graphs with the C++ STL as the input graph for our breadth first search function, so if you haven't read that article yet or need a quick refresher, go have a look.

With that done its time to get down to business. As mentioned above, in order to perform our BFS we need a way to keep track of which vertexes we've already been to, and which ones we haven't seen yet. To do this we will use an std::map of vertex name -> boolean values. We're also going to keep track of which vertex we came from previously: this will allow us to rebuild our search path. For this we will also use an std::map.

The first think we need to do is declare our variables and containers:

void breadthFirstSearch(Graph& G, char start, char fin)
{
   bool success = false;
   char current = start;
   char child, next;
   std::map<char, bool> seen; //which vertexes have been visited
   std::map<char, char> camefrom; //for rebuilding bath
   std::queue<char> searchqueue; //search queue for BFS = FIFO

Next, we add start to the queue and mark it as seen:

   searchqueue.push(current); //push initial vertex
   seen[current] = true; //mark as visited.

After that, we proceed with the while loop as outlined in the algorithm pseudo code above:

while (!searchqueue.empty())
{
   current = searchqueue.front(); //get the first item on the queue
   searchqueue.pop(); //remove it from the queue
   if (current == fin) //is this our search target?
   {
      success = true; //hooray
     break; //we can stop looking
   }
   for (auto u : G.adjList[current]) //for every adjacent vertex of current
   {
     child = u.first;
     if (seen[child] == false) //if we havent yet visited this vertex
     {
       searchqueue.push(child); //add it to the queue
       seen[child] = true; //no need to see it twice.
       camefrom[child] = current;
     }
   }
}

Now if we wanted to, we could just output whether success is true or not. We're going to go one step further and will output the traversal path through the graph that led to our successful search:

if (success)
{
  cout<<"A path from "<<start<<" to "<<fin<<" was found.\n";
  next = fin;
  std::vector<char> path;
  while (next != start)
  {
    path.push_back(next);
    next = camefrom[next];
  }
  reverse(path.begin(), path.end());
  cout<<"Path Length: "<<path.size()+1;
  cout<<"\nPath: "<<start;
  for (auto n : path)
  {
    cout<<" -> "<<n;
  }
  cout<<endl;
} else {
  cout<<"\nNo such path Exists. ("<<start<<" -> "<<fin<<")\n";
}
}

To test our algorithm, we use the following driver program to build a graph and pass it to breadthFirstSearch():

int main(int argc, char *argv[])
{
  Graph G(6);
  G.addEdge('A', 'B', 0);
  G.addEdge('A', 'C', 0);
  G.addEdge('B', 'C', 0);
  G.addEdge('C', 'E', 0);
  G.addEdge('D', 'E', 0);
  G.addEdge('D', 'F', 0);
  G.addEdge('E', 'F', 0);
  G.showAdjList();
  breadthFirstSearch(G, 'A', 'D');
  return 0;
}

Output:
A: B C 
B: A C 
C: A B E 
D: E F 
E: C D F 
F: D E 

A path from A to D was found.
Path Length: 4
Path: A -> C -> E -> D

There you have it: Breadth First Search and Single Source Shortest Path!

As always, the full code for the example shown in this article is available on my github:

https://github.com/maxgoren/examples/blob/main/graphing-bfs.cpp

 

---