BFS IN GRAPH

//////// BFS IN GRAPHS /////////////

/// breadth first = tranverse technique to printing by edges connected 
 // APPROACH = track the vidited node , queue data structure willl be used ,  

#include <iostream>
#include <unordered_map>
#include <list>
#include <queue> // Include for using the queue data structure
using namespace std; // Allows us to use standard library names without the std:: prefix

// Class to represent a graph
class Graph {
public:
    // Adjacency list representation of the graph using an unordered_map
    unordered_map<int, list<int>> adj;

    // Function to add an edge to the graph
    void addEdge(int u, int v) {
        // Add an edge from vertex u to vertex v
        adj[u].push_back(v);
        // For undirected graph, add an edge from vertex v to vertex u
        adj[v].push_back(u);
    }

    // Function to perform BFS traversal from a given starting node
    void bfs(int start) {
        // Create a queue to help with the BFS traversal
        queue<int> q;
        // Create a map to keep track of visited nodes
        unordered_map<int, bool> visited;

        // Start by marking the starting node as visited and enqueue it
        visited[start] = true; // Mark the starting node as visited
        q.push(start); // Enqueue the starting node

        // Continue the BFS until the queue is empty
        while (!q.empty()) {
            // Dequeue a vertex from the queue and print it
            int node = q.front(); // Get the front node of the queue
            cout << node << " "; // Print the current node
            q.pop(); // Remove the node from the queue

            // Iterate through all the adjacent vertices of the dequeued vertex
            for (int neighbor : adj[node]) {
                // If the neighbor hasn't been visited yet
                if (!visited[neighbor]) {
                    // Mark it as visited and enqueue it
                    visited[neighbor] = true; // Mark the neighbor as visited
                    q.push(neighbor); // Enqueue the neighbor
                }
            }
        }
    }
};

int main() {
    Graph g; // Create a graph object

    // Adding edges to the graph
    g.addEdge(0, 1); // Add edge between vertex 0 and vertex 1
    g.addEdge(0, 2); // Add edge between vertex 0 and vertex 2
    g.addEdge(1, 2); // Add edge between vertex 1 and vertex 2
    g.addEdge(1, 3); // Add edge between vertex 1 and vertex 3
    g.addEdge(2, 4); // Add edge between vertex 2 and vertex 4
    g.addEdge(3, 4); // Add edge between vertex 3 and vertex 4

    // Perform BFS starting from vertex 0
    cout << "BFS traversal starting from vertex 0: ";
    g.bfs(0); // Call the BFS function
    cout << endl; // Print a newline for better formatting

    return 0; // Indicate that the program ended successfully
}