bfswithq.cpp

#include <iostream>
using namespace std;
/*
class Queue {
    int* arr;
    int front;
    int rear;
    int size;
public:
    Queue(int n) {
        size = n;
        arr = new int[size];
        front = 0;
        rear = 0;
    }

    void push(int val) {
        if (rear < size) {
            arr[rear++] = val;
        } else {
            cout << "Queue Overflow\n";
        }
    }

    int pop() {
        if (front == rear) {
            cout << "Queue Underflow\n";
            return -1;
        } else {
            int val = arr[front];
            front++;
            return val;
        }
    }

    bool isEmpty() {
        return front == rear;
    }

    ~Queue() {
        delete[] arr;
    }
};

void bfs(int** adj, int V, int start) {
    bool* visited = new bool[V];
    for (int i = 0; i < V; i++) {
        visited[i] = false;
    }

    Queue q(V);
    q.push(start);
    visited[start] = true;

    while (!q.isEmpty()) {
        int node = q.pop();
        cout << node << " ";

        for (int i = 0; i < V; i++) {
            if (adj[node][i] == 1 && !visited[i]) {
                q.push(i);
                visited[i] = true;
            }
        }
    }

    delete[] visited;
}
*/

class Queue{
    int *arr;
    int front;
    int rear;
    int size;
    int count;
    public:
    Queue(int v){
        size=v;
        front=0;
        rear=0;
        count=0;
        arr=new int[size];
    }
    void push(int val){
        if(count==size){
            cout<<"queue full \n";
        }else{
            arr[rear]=val;
            rear=(rear+1)%size;
            count++;
        }
    }
    int pop(){
        if(count==0){
            cout<<"queue empty \n";
            return -1;
        }else{
            int val=arr[front];
            front=(front+1)%size;
            count--;
            return val;
        }
    }
    bool isempty(){
        return count==0;
    }
    ~Queue(){
        delete[] arr;
    }
};

void bfs(int **adj,int vertices,int start){
    bool* visited=new bool[vertices];
    for(int i=0;i<vertices;i++){
        visited[i]=false;
    }
    Queue qu(vertices);
    qu.push(start);
    visited[start]=true;
    while(!qu.isempty()){
        int node=qu.pop();
        cout<<node<<" ";
        for(int i=0;i<vertices;i++){
            if(adj[node][i]==1 && !visited[i]){
                qu.push(i);
                visited[i]=true;
            }
        }
    }
    delete[] visited;
}

int main() {
    int V, E;
    cout << "Enter number of vertices and edges: ";
    cin >> V >> E;

    int** adj = new int*[V];
    for (int i = 0; i < V; i++) {
        adj[i] = new int[V];
        for (int j = 0; j < V; j++) {
            adj[i][j] = 0;
        }
    }

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

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

    cout << "BFS Traversal: ";
    bfs(adj, V, start);
    cout << endl;

    for (int i = 0; i < V; i++) {
        delete[] adj[i];
    }
    delete[] adj;

    return 0;
}