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>

using namespace std;

vector<vector<int>> adjList;
vector<bool> visited;

void bfs(int startNode) {
    queue<int> q;

    visited[startNode] = true;
    q.push(startNode);

    while (!q.empty()) {
        int currentNode = q.front();
        q.pop();

        cout << "Visiting node: " << currentNode << endl;

        for (int adjacent : adjList[currentNode]) {
            if (!visited[adjacent]) {
                visited[adjacent] = true;
                q.push(adjacent);
            }
        }
    }
}

int main() {
    // Initialize adjacency list and visited vector
    adjList = {{1, 3}, {0, 2}, {1, 3}, {0, 2}};
    visited.resize(4, false);

    // Perform BFS from the first node
    bfs(0);

    return 0;
}

Example USACO Silver Problems

Here are some example USACO Silver problems that utilize Breadth-First Search:

   2017 January Silver Problem 3: Cow Navigation
   2018 December Silver Problem 2: Mooyo Mooyo
   2020 February Silver Problem 1: Triangles

Example USACO Gold Problems

Here are some example USACO Gold problems that utilize Breadth-First Search:

   2015 December Gold Problem 1: Moocast
   2019 December Gold Problem 2: Cow Land
   2020 January Gold Problem 2: Milk Visits