What is Breadth-First Search in C++?

Can you explain what Breadth-First Search is in C++?

Sure! Breadth-First Search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at a selected node and explores all its neighbors at the present depth prior to moving on to nodes at the next depth level.

How do I implement BFS in C++?

To implement BFS in C++, you can use a queue to keep track of nodes to visit. Here's a simple example:

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

void bfs(int start, const vector<vector<int>>& graph) {
    vector<bool> visited(graph.size(), false);
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " ";

        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

This code initializes a queue, marks the starting node as visited, and explores each node's neighbors.

What are some use cases for BFS?

BFS is commonly used in scenarios like finding the shortest path in unweighted graphs, web crawling, and social network analysis. It's also useful in solving puzzles like the shortest path in mazes.