BFS Code in C++

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

using namespace std;

// Graph class using adjacency list representation
class Graph {
    int V; // Number of vertices

    // Pointer to an array containing adjacency lists
    vector<vector<int>> adj;

public:
    Graph(int v); // Constructor
    void addEdge(int v, int w); // Add an edge to the graph
    void BFS(int startVertex); // Breadth-first search starting from a given vertex
};

// Constructor
Graph::Graph(int v) {
    this->V = v;
    adj.resize(v);
}

// Add an edge to the graph
void Graph::addEdge(int v, int w) {
    adj[v].push_back(w);
}

// Breadth-first search
void Graph::BFS(int startVertex) {
    // Create a boolean array to track visited vertices
    vector<bool> visited(V, false);

    // Create a queue for BFS
    queue<int> q;

    // Mark the current vertex as visited and enqueue it
    visited[startVertex] = true;
    q.push(startVertex);

    while (!q.empty()) {
        // Dequeue a vertex from the queue and print it
        int vertex = q.front();
        cout << vertex << " ";
        q.pop();

        // Get all adjacent vertices of the dequeued vertex
        // If an adjacent vertex is not visited yet, mark it visited and enqueue it
        for (int i : adj[vertex]) {
            if (!visited[i]) {
                visited[i] = true;
                q.push(i);
            }
        }
    }
}

int main() {
    // Create a graph
    Graph g(6);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 4);
    g.addEdge(3, 5);
    g.addEdge(4, 5);

    cout << "Breadth-First Traversal (starting from vertex 0): ";
    g.BFS(0);

    return 0;
}