Breadth-First Search

Breadth-First Search (BFS)

Breadth-First Search (BFS) is an algorithm for searching a tree or graph data structure for a node that meets a set of criteria. It starts at the tree’s root or graph and searches/visits all nodes at the current depth level before moving on to the nodes at the next depth level. <ref name=“geeksforgeeks”>https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/</ref>

How it works

BFS uses a queue data structure to keep track of the nodes to be visited. It also uses an array or a set to mark the nodes that have been visited, to avoid revisiting them.

The algorithm works as follows:

Choose a starting node, mark it as visited, and add it to the queue. While the queue is not empty: Dequeue a node from the queue and process it (e.g., print its value). Enqueue all its adjacent nodes that have not been visited and mark them as visited. Repeat step 2 until the queue is empty.

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:

- [Navigation] - [Pails] - [[1]] - [[2]] - [Bucket List]