Breadth First Search and Single Source Shortest Path
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
-
Simple DB Migration with JDBC
-
Welcome to CodeBlahger, A Blahging Platform for Programmers.
-
Design Patterns: The Façade Pattern
-
The Interpreter Pattern: Implementing Interpreters the OOP way
-
Parsing Right-Associative Operators with Recursive Descent
-
BST Iterators Revisited: No Parent Pointer, No Stack, No Problem
-
Deleting Arbitrary Values from Binary Search Trees
-
Solving the N Queens Problem with Breadth First Search
-
Performing the Knights Tour in Linear Time
-
Knuth's Algorithm X For the Exact Cover Problem
Leave A Comment