When in survival (well, it's the twenty-first century, so let's say a survival video game), it's best not to wander too far from camp, otherwise you might risk getting lost. What you might do instead is wander in the area closest to camp, then as you become more comfortable with the area, increase the perimeter of space you are able to confidently explore.

In another way of saying, as the perimeter of familiarity increases, you are widening the breadth of your familiarity with the area.

By searching the area this way, you are subtlety conducting an algorithm known as breadth-first search.

Assumptions

What is Breadth-First Search?

Breadth-first search (BFS) is a searching algorithm designed to traverse a tree by exploring the nearest nodes from the starting node first, then branching out to the next nearest nodes.

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/algs/BFS_01.png" alt="BFS diagram" style="width:500px;max-width:95%;">

</div>

While breadth-first search is an algorithm for searching a graph, it is truly more of a strategy for searching a graph; it acts as a base "template" for solving similar graph problems. Using the strategy that BFS provides us with allows us to do things like find connected components and the shortest path through a graph (think GPS directions) with only slight modifications to the base code! 

 /* pseudo-code */

 // Refresher of what a basic graph might look like.
 class Graph {
   // A list of lists for the nodes + edges.
   List[] adj;
   int size;
 }

 function BFS( Graph G, int startVert ) {
   // (1).
   boolean[] visited = new boolean[G.size];
   // Create a new queue.
   Queue q = new Queue();
   
   visited[ startVert ] = true;

   q.enqueue( startVert );
   // Continue until all nodes have been visited.
   while ( q is not empty ) {
     int vert = q.dequeue();
     // (2).
     for ( int adjV in G.adj[ vert ] ) {
       // (3).
       if ( not visited[adjV] ) {
         visited[ adjV ] = true;
         q.enqueue( adjV );
       }
     }
   }
 }

Going over the steps in the comments:

  1. We want to keep an array the size of the graph to know when we've already seen a particular vertex. Without visited[], the algorithm might get caught in an infinite loop!*
  2. Foreshadowing to the next point, any vertices in the queue are also vertices that we have not yet visited. When a vertex V is removed from the queue, we look at every vertex that shares an edge with V.
  3. Lastly, if the vertex that shares an edge with V has not been visited yet, we mark it as visited and add it to the queue. If it has already been visited, then this step is skipped over, and the algorithm continues.

There is a similar algorithm to this that uses stacks instead of queues and it's called Depth-first search. The difference in the FIFO and LIFO (FILO) nature of the two is what differentiates them.

> *This is not true for using BFS on Trees, but on a Graph that contains a cycle, it is a real concern.

Analysis of BFS

Performance Memory
O(V + E) O(V)

Looking at the performance chart of BFS, you might notice that it is not the typical order of n comparison. This is because the performance of BFS, and many other graph algorithms, are dependent on both the number of vertices and the number of edges.

To break down why this is the case, let's examine the algorithm deeper.

  1. To successfully perform BFS, the algorithm must look at every vertex once. Hence, it is directly dependent on the number of vertices, V.
  2. When each vertex is being looped over, all of the edges that lead out of that vertex are also examined to find any unvisited nodes. In the worst case, every node in the graph could have V - 1 edges, one to every other vertex. In the converse, each vertex V might only have a singular edge leading from it. As you can see, this creates a lot of variance, all highly dependent on the number of edges, E.

From these two points, it is clear that the performance of BFS is dependent on both the total vertices and the total edges. As a result, the performance of breadth-first search is O(V + E).

> The reason that it is not O(V*E) is that not all nodes will have the same number of edges; each node has an independent amount of edges from the other nodes on the graph.

Breadth-First Search Example

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/algs/BFS_02.png" alt="Exploring a graph using bfs." style="max-width:95%;"> </div>

When to use BFS

When using BFS you will find yourself using the BFS strategy more than the actual algorithm; BFS doesn't return any interesting value or modify any data in its basic implementation. Much more likely is that you would adapt the algorithm for your needs. For instance, if you were looking for a particular item in a graph, you might insert an additional check for the particular node in each iteration. BFS is very helpful for algorithms dealing with shortest distances, like Dijkstra's Algorithm. These have useful applications in GPS where you might want the fastest route to your destination.

> Often times, these applications are combined with weighted graphs, where the edges contain values, such as distance between each vertex.

Further Resources