C++ • GRAPH TRAVERSAL Breadth-First Search (BFS)

C++ • GRAPH TRAVERSAL

Breadth-First Search (BFS)

ALGORITHM

Breadth-First Search

TIME COMPLEXITY

O(V + E)

SPACE COMPLEXITY

O(V)

STRUCTURE

Queue

C++ Implementation

bfs_graph.cpp

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

class GraphBFS
{
    int V; // Number of vertices
    vector<vector<int>> adj; // Adjacency list

public:

    // Constructor
    GraphBFS()
    {
        V = 0;
    }

    // Input function to read graph structure
    void input()
    {
        int E;
        cout << "Enter number of vertices: ";
        cin >> V;
        adj.resize(V);

        cout << "Enter number of edges: ";
        cin >> E;

        cout << "Enter edges (u v for undirected edge):\n";
        for (int i = 0; i < E; i++)
        {
            int u, v;
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
    }

    // Breadth-First Search function
    void bfs(int startNode)
    {
        vector<bool> visited(V, false);
        queue<int> q;

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

        cout << "BFS Traversal: ";

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

            for (int neighbor : adj[curr])
            {
                if (!visited[neighbor])
                {
                    visited[neighbor] = true;
                    q.push(neighbor);
                }
            }
        }
        cout << endl;
    }
};

int main()
{
    GraphBFS obj;

    obj.input();
    
    int start;
    cout << "Enter starting vertex: ";
    cin >> start;

    obj.bfs(start);

    return 0;
}

Sample Input

Enter number of vertices: 5
Enter number of edges: 5
Enter edges (u v for undirected edge):
0 1
0 2
1 3
1 4
2 4
Enter starting vertex: 0

Output

BFS Traversal: 
0 1 2 3 4 

Line-by-Line Explanation

Code

Meaning

#include <iostream>

Includes standard input/output stream functions.

#include <vector>

Includes dynamic array support for adjacency list representation.

#include <queue>

Includes Queue data structure required for level-order traversal.

class GraphBFS

Creates a class named GraphBFS to encapsulate graph data and traversal methods.

vector<vector<int>> adj;

Adjacency list representation storing neighbors for each vertex.

GraphBFS()

Class constructor that initializes vertex count to zero.

void input()

Reads the number of vertices, edges, and connections from the user.

vector<bool> visited(V, false);

Tracks which vertices have already been visited to prevent infinite loops.

queue<int> q;

FIFO queue used to process vertices level by level.

q.push(startNode);

Enqueues the starting vertex and marks it as visited.

while (!q.empty())

Continues visiting nodes as long as there are elements remaining in the queue.

GraphBFS obj;

Instantiates the GraphBFS object and triggers the constructor.

return 0;

Signals successful program execution.

How Breadth-First Search (BFS) works: BFS explores a graph level by level starting from a chosen source vertex. It visits all immediate neighbors of the current vertex first, pushes them into a queue, and then processes those neighbors in the order they were discovered until all reachable nodes are visited.