BFS

Time complexity: O(V+E)

Space complexity: O(V)

Data type: Graphs, Trees

Visualization

React Flow
Click any two vertices to connect them
Shift+click on the node to set it as "start"

Definition

Breadth-First Search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the root node (or any arbitrary node in case of a graph) and explores all neighbor nodes at the present depth prior to moving on to nodes at the next depth level.

Constraints

  • Graph can be directed or undirected
  • Works well for unweighted graphs or finding shortest paths in unweighted graphs
  • For disconnected graphs, needs to be run on each component

Step-by-step explanation

Arguments:

  • Graph representation - graph
  • Starting node - start
  • Visited array (optional) - visited

Explanation:

  • Create a queue and enqueue the starting node
  • Mark the starting node as visited
  • While the queue is not empty:
    • Dequeue a node from the front
    • Process the node (print, store, etc.)
    • Enqueue all adjacent nodes that haven't been visited and mark them as visited
  • The algorithm explores all nodes at the current depth before moving to the next level

Returns:

Depends on implementation - can return traversal order, shortest path distances, or other graph properties

Example

1
#include <iostream>
2
#include <vector>
3
#include <queue>
4


5
void bfs(int start, const std::vector<std::vector<int>>& adj, std::vector<bool>& visited) {
6
    std::queue<int> q;
7
    q.push(start);
8
    visited[start] = true;
9


10
    while (!q.empty()) {
11
        int u = q.front();
12
        q.pop();
13
        std::cout << u << " ";
14


15
        for (int v : adj[u]) {
16
            if (!visited[v]) {
17
                visited[v] = true;
18
                q.push(v);
19
            }
20
        }
21
    }
22
}