Breadth-First Search (BFS) is a fundamental algorithm in computer science used for traversing or searching tree or graph data structures. It explores vertices layer by layer, ensuring that all nodes at a given depth are visited before moving to nodes at the next depth level. BFS has numerous applications, including finding the shortest path in unweighted graphs, web crawling, and network broadcasting.

Program Structure

The C++ program to implement BFS traversal is organized into the following key components:

• Graph Representation: Using an adjacency list to represent the graph.
• BFS Implementation: Utilizing a queue to manage the traversal order.
• Main Function: Handling user input, constructing the graph, invoking BFS, and displaying the results.

Code Implementation

The following C++ program implements BFS traversal on a graph using an adjacency list representation:

// BFS Traversal of a Graph in C++
// This program performs Breadth-First Search (BFS) traversal on a graph.

#include <iostream>
#include <vector>
#include <list>
#include <queue&gt>

using namespace std;

// Class to represent a graph using adjacency list representation
class Graph {
    int V; // Number of vertices
    list *adj; // Pointer to an array containing adjacency lists

public:
    Graph(int V); // Constructor
    void addEdge(int v, int w); // Function to add an edge to graph
    void BFS(int s); // Function to perform BFS traversal from a given source s
};

// Constructor
Graph::Graph(int V) {
    this->V = V;
    adj = new list[V];
}

// Function to add an edge to the graph
void Graph::addEdge(int v, int w) {
    adj[v].push_back(w); // Add w to v’s list
    adj[w].push_back(v); // Since the graph is undirected, add v to w’s list
}

// Function to perform BFS traversal from a given source s
void Graph::BFS(int s) {
    // Mark all vertices as not visited
    vector visited(V, false);

    // Create a queue for BFS
    queue queue;

    // Mark the current node as visited and enqueue it
    visited[s] = true;
    queue.push(s);

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

        // Get all adjacent vertices of the dequeued vertex s
        // If an adjacent vertex has not been visited, mark it visited and enqueue it
        for(auto adjVertex = adj[s].begin(); adjVertex != adj[s].end(); ++adjVertex) {
            if(!visited[*adjVertex]) {
                visited[*adjVertex] = true;
                queue.push(*adjVertex);
            }
        }
    }
}

int main() {
    int V, E;
    cout << "BFS Traversal of a Graph using C++\n";
    cout << "-------------------------------\n";
    cout << "Enter the number of vertices: ";
    cin >> V;
    cout << "Enter the number of edges: ";
    cin >> E;

    Graph g(V);

    cout << "Enter the edges in the format (source destination):\n";
    for(int i = 0; i < E; i++) {
        int src, dest;
        cin >> src >> dest;
        g.addEdge(src, dest);
    }

    int start;
    cout << "Enter the starting vertex for BFS traversal: ";
    cin >> start;

    cout << "\nBFS Traversal starting from vertex " << start << ":\n";
    g.BFS(start);
    cout << endl;

    return 0;
}
        

Program Explanation

The program implements BFS traversal on an undirected graph using an adjacency list. Below is a detailed breakdown of its components:

1. Graph Representation

The graph is represented using an adjacency list, which is an array of lists. Each index of the array represents a vertex, and each element in the list at that index represents an adjacent vertex.

list<int> *adj;

2. Adding Edges

The addEdge function adds an undirected edge between two vertices by adding each vertex to the other’s adjacency list.

void Graph::addEdge(int v, int w) {
    adj[v].push_back(w); // Add w to v’s list
    adj[w].push_back(v); // Since the graph is undirected, add v to w’s list
}
        

3. BFS Traversal Function

The BFS function performs the BFS traversal starting from a given source vertex. It utilizes a queue to keep track of the order in which vertices should be visited and a visited vector to track which vertices have already been visited.

void Graph::BFS(int s) {
    vector<bool> visited(V, false); // Initialize all vertices as not visited
    queue<int> queue; // Create a queue for BFS

    visited[s] = true; // Mark the source node as visited
    queue.push(s); // Enqueue the source node

    while(!queue.empty()) {
        s = queue.front(); // Dequeue a vertex from queue
        cout << s << " "; // Print the dequeued vertex
        queue.pop();

        // Get all adjacent vertices of the dequeued vertex
        for(auto adjVertex = adj[s].begin(); adjVertex != adj[s].end(); ++adjVertex) {
            if(!visited[*adjVertex]) {
                visited[*adjVertex] = true; // Mark as visited
                queue.push(*adjVertex); // Enqueue the vertex
            }
        }
    }
}
        

4. Main Function

The main function handles user input, constructs the graph by adding edges, and initiates the BFS traversal from the specified starting vertex.

int main() {
    int V, E;
    cout << "BFS Traversal of a Graph using C++\n";
    cout << "-------------------------------\n";
    cout << "Enter the number of vertices: ";
    cin >> V;
    cout << "Enter the number of edges: ";
    cin >> E;

    Graph g(V); // Create a graph with V vertices

    cout << "Enter the edges in the format (source destination):\n";
    for(int i = 0; i < E; i++) {
        int src, dest;
        cin >> src >> dest;
        g.addEdge(src, dest); // Add the edge to the graph
    }

    int start;
    cout << "Enter the starting vertex for BFS traversal: ";
    cin >> start;

    cout << "\nBFS Traversal starting from vertex " << start << ":\n";
    g.BFS(start); // Perform BFS traversal
    cout << endl;

    return 0;
}
        

Program Documentation

Detailed documentation for each component of the program:

Class: Graph

• Purpose: Represents a graph using an adjacency list and provides methods to add edges and perform BFS traversal.
• Members:
  • int V; – Number of vertices in the graph.
  • list<int> *adj; – Pointer to an array of adjacency lists.
• Functions:
  • Graph(int V); – Constructor to initialize the graph with V vertices.
  • void addEdge(int v, int w); – Adds an undirected edge between vertex v and vertex w.
  • void BFS(int s); – Performs BFS traversal starting from vertex s.

Function: BFS

• Purpose: Performs Breadth-First Search traversal of the graph starting from a given source vertex.
• Parameters:
  • int s – The starting vertex for BFS traversal.
• Returns: None. Prints the BFS traversal order to the console.
• Logic:
  1. Initialize all vertices as not visited.
  2. Create a queue and enqueue the starting vertex after marking it as visited.
  3. While the queue is not empty:
     • Dequeue a vertex from the queue and print it.
     • Iterate through all adjacent vertices of the dequeued vertex.
     • If an adjacent vertex has not been visited, mark it as visited and enqueue it.

Function: addEdge

• Purpose: Adds an undirected edge between two vertices in the graph.
• Parameters:
  • int v – The source vertex.
  • int w – The destination vertex.
• Returns: None.
• Logic:
  1. Add vertex w to the adjacency list of vertex v.
  2. Add vertex v to the adjacency list of vertex w (since the graph is undirected).

Function: main

• Purpose: Acts as the entry point of the program, handling user input and initiating BFS traversal.
• Parameters: None.
• Returns: 0 upon successful execution.
• Logic:
  1. Prompts the user to enter the number of vertices and edges.
  2. Reads the edges and constructs the graph using the addEdge function.
  3. Prompts the user to enter the starting vertex for BFS traversal.
  4. Calls the BFS function to perform the traversal and displays the order.

How the Program Works

1. Input Handling: The program begins by asking the user to input the number of vertices (V) and edges (E). It then prompts the user to enter each edge in the format (source destination), which are used to construct the adjacency list.
2. Graph Construction: Using the addEdge function, the program builds the adjacency list for the graph, ensuring that each undirected edge is represented in both directions.
3. BFS Traversal: The user is prompted to enter the starting vertex for BFS. The BFS function is then called with this vertex, performing the traversal and printing the order in which vertices are visited.
4. Output: The program outputs the sequence of vertices visited during the BFS traversal, providing a clear view of the traversal order.

Example Execution

Consider the following example input and output:

BFS Traversal of a Graph using C++
-------------------------------
Enter the number of vertices: 5
Enter the number of edges: 6
Enter the edges in the format (source destination):
0 1
0 2
1 3
1 4
2 4
3 4
Enter the starting vertex for BFS traversal: 0

BFS Traversal starting from vertex 0:
0 1 2 3 4 
        

Explanation: The BFS traversal starts at vertex 0, then visits its adjacent vertices 1 and 2. From vertex 1, it visits vertices 3 and 4. Vertex 2 also points to vertex 4, but since vertex 4 has already been visited, it is not enqueued again. The traversal order is therefore 0, 1, 2, 3, 4.

Conclusion

Breadth-First Search (BFS) is an essential algorithm for traversing and searching through graph structures. This C++ implementation effectively demonstrates BFS traversal using an adjacency list and a queue, ensuring that all vertices are visited in the correct order. Understanding and implementing BFS is crucial for solving various real-world problems, including network routing, social network analysis, and pathfinding in gaming applications.