Cover Image for BFS Code in C++

BFS Code in C++

Here’s a C++ implementation of a breadth-first search (BFS) algorithm for traversing a graph. In this example, I’ll use an adjacency list to represent the graph.

#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;

    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;

// Add an edge to the graph
void Graph::addEdge(int v, int 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;

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

        // 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;

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): ";

    return 0;

In this code:

  • We define a Graph class to represent the graph using an adjacency list. The constructor takes the number of vertices (V) as a parameter.
  • The addEdge method is used to add edges to the graph.
  • The BFS method performs breadth-first search starting from a given vertex. It uses a boolean array visited to keep track of visited vertices and a queue q for the BFS traversal.
  • In the main function, we create a graph and add edges to it. Then, we call the BFS method to perform a breadth-first traversal starting from vertex 0.

The output will be the breadth-first traversal of the graph starting from vertex 0.


The Tech Thunder

The Tech Thunder

The Tech Thunder