C++ Program for BFS (Breadth-First Search) with Example

A C++ program for BFS uses a queue to explore graph nodes level by level, starting from a source node, visiting neighbors before moving deeper. The core code uses a while loop with a queue and a visited array to track explored nodes.

Examples

InputGraph edges: 0-1, 0-2, 1-2, 2-0, 2-3, 3-3; Start node: 2

Output2 0 3 1

InputGraph edges: 0-1, 1-2, 2-3; Start node: 0

Output0 1 2 3

InputGraph edges: 0-1; Start node: 1

Output1

How to Think About It

To perform BFS, think of exploring a graph like spreading out in waves from a starting point. Use a queue to keep track of nodes to visit next. Mark nodes as visited when you add them to the queue to avoid repeats. Then, repeatedly take the front node from the queue, visit it, and add its unvisited neighbors to the queue until no nodes remain.

Algorithm

1

Initialize a queue and a visited list for all nodes as false

2

Mark the start node as visited and enqueue it

3

While the queue is not empty:

4

Dequeue a node and process it (e.g., print it)

5

For each neighbor of this node, if not visited, mark visited and enqueue

6

End when all reachable nodes are processed

Code

cpp

#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;
    visited[start] = true;
    q.push(start);

    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);
            }
        }
    }
}

int main() {
    vector<vector<int>> graph = {
        {1, 2}, // neighbors of node 0
        {2},    // neighbors of node 1
        {0, 3}, // neighbors of node 2
        {3}     // neighbors of node 3
    };
    bfs(2, graph);
    return 0;
}

Output

2 0 3 1 

Dry Run

Let's trace BFS starting from node 2 on the example graph.

1

Initialize

visited = [false, false, false, false], queue = []

2

Start node 2

visited = [false, false, true, false], queue = [2]

3

Process node 2

Print 2; neighbors = 0, 3; mark visited[0]=true, visited[3]=true; queue = [0, 3]

4

Process node 0

Print 0; neighbors = 1, 2; 2 already visited; mark visited[1]=true; queue = [3, 1]

5

Process node 3

Print 3; neighbors = 3; already visited; queue = [1]

6

Process node 1

Print 1; neighbors = 2; already visited; queue = []

Queue	Visited	Output
[2]	[false, false, true, false]
[0, 3]	[true, false, true, true]	2
[3, 1]	[true, true, true, true]	2 0
[1]	[true, true, true, true]	2 0 3
[]	[true, true, true, true]	2 0 3 1

Why This Works

Step 1: Use a queue to explore nodes

The queue stores nodes to visit next, ensuring nodes are processed in the order they are discovered.

Step 2: Mark nodes visited when enqueued

Marking nodes as visited when added to the queue prevents revisiting and infinite loops.

Step 3: Process neighbors level by level

BFS visits all neighbors of a node before moving deeper, exploring the graph in layers.

Alternative Approaches

Recursive BFS using helper function

cpp

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

void bfsHelper(queue<int>& q, vector<bool>& visited, const vector<vector<int>>& graph) {
    if (q.empty()) return;
    int node = q.front();
    q.pop();
    cout << node << " ";
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            visited[neighbor] = true;
            q.push(neighbor);
        }
    }
    bfsHelper(q, visited, graph);
}

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

int main() {
    vector<vector<int>> graph = {{1,2},{2},{0,3},{3}};
    bfs(2, graph);
    return 0;
}

Uses recursion to process the queue, but may cause stack overflow on large graphs.

BFS using adjacency matrix

cpp

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

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

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " ";
        for (int i = 0; i < n; i++) {
            if (matrix[node][i] == 1 && !visited[i]) {
                visited[i] = true;
                q.push(i);
            }
        }
    }
}

int main() {
    vector<vector<int>> matrix = {
        {0,1,1,0},
        {0,0,1,0},
        {1,0,0,1},
        {0,0,0,1}
    };
    bfs(2, matrix);
    return 0;
}

Uses adjacency matrix instead of list; simpler for dense graphs but uses more memory.

Complexity: O(V + E) time, O(V) space

Time Complexity

BFS visits each vertex once and checks all edges once, so time is proportional to vertices plus edges.

Space Complexity

The queue and visited array use space proportional to the number of vertices.

Which Approach is Fastest?

Adjacency list BFS is faster and uses less memory for sparse graphs compared to adjacency matrix BFS.

Approach	Time	Space	Best For
Adjacency List BFS	O(V + E)	O(V)	Sparse graphs, memory efficient
Adjacency Matrix BFS	O(V^2)	O(V^2)	Dense graphs, simple implementation
Recursive BFS	O(V + E)	O(V) + call stack	Small graphs, educational use