Breadth-First Search

Breadth-First Search

Breadth-First Search (BFS) is a graph traversal algorithm that explores all the vertices of a graph in breadthward (layer-by-layer) motion. BFS is particularly useful for finding the shortest path between two nodes in an unweighted graph.

Algorithm

   Start at the source node and mark it as visited.
   Enqueue the source node into a queue.
   While the queue is not empty:
   a. Dequeue the front node from the queue.
   b. Process the dequeued node (e.g., print its value).
   c. For each adjacent node of the dequeued node, if it is not visited, mark it as visited and enqueue it.

Complexity

The time complexity of BFS is O(|V| + |E|), where |V| is the number of nodes and |E| is the number of edges in the graph. This is because every node and every edge will be explored in the worst case.

The space complexity of BFS is O(|V|), where |V| is the number of nodes in the graph. This is because the queue can hold up to |V| nodes in the worst case.

Example C++ code

Here is an example of implementing BFS in C++ using STL containers:

#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;

// A simple graph class
class Graph {
  int V; // number of vertices
  vector<int> *adj; // adjacency list
public:
  // constructor
  Graph(int V) {
    this->V = V;
    adj = new vector<int>[V];
  }

  // add an edge from u to v
  void addEdge(int u, int v) {
    adj[u].push_back(v);
  }

  // BFS starting from s
  void BFS(int s) {
    queue<int> q; // queue for BFS
    set<int> visited; // set for marking visited nodes

    // mark s as visited and enqueue it
    visited.insert(s);
    q.push(s);

    while (!q.empty()) {
      // dequeue a node and print it
      int v = q.front();
      q.pop();
      cout << v << " ";

      // enqueue all adjacent nodes that are not visited
      for (int u : adj[v]) {
        if (visited.find(u) == visited.end()) {
          visited.insert(u);
          q.push(u);
        }
      }
    }
    cout << endl;
  }
};

// driver code
int main() {
  // create a graph with 6 vertices
  Graph g(6);

  // add some edges
  g.addEdge(0, 1);
  g.addEdge(0, 2);
  g.addEdge(1, 3);
  g.addEdge(2, 3);
  g.addEdge(2, 4);
  g.addEdge(3, 5);
  g.addEdge(4, 5);

  // BFS starting from node 0
  g.BFS(0);

  return 0;
}

USACO problems for BFS

Here are some USACO problems that can be solved using BFS:

• Cow Navigation
• Milk Pails
• MooTube
• Moocast
• The Bucket List