bfs&dfs.cpp

#include <iostream>
using namespace std;

class Graph {
    int **adjMatrix;
    int vertices;

public:
    void createGraph(int v, int e) {
        vertices = v;
        adjMatrix = new int*[vertices];
        for (int i = 0; i < vertices; i++) {
            adjMatrix[i] = new int[vertices];
            for (int j = 0; j < vertices; j++) {
                adjMatrix[i][j] = 0;
            }
        }

        int u, ver;
        for (int i = 0; i < e; i++) {
            cout << "Enter edge " << i + 1 << " (format: u v): ";
            cin >> u >> ver;

            if (u < 0 || u >= vertices || ver < 0 || ver >= vertices) {
                cout << "Invalid edge! Vertex numbers should be between 0 and " << vertices - 1 << ".\n";
                i--; 
                continue;
            }

            adjMatrix[u][ver] = 1;
            adjMatrix[ver][u] = 1; // Remove for directed graph
        }
    }

    void dfs(int start, int *visited) {
        cout << start << " ";
        visited[start] = 1;

        for (int i = 0; i < vertices; i++) {
            if (adjMatrix[start][i] == 1 && !visited[i]) {
                dfs(i, visited);
            }
        }
    }

    void bfs(int start) {
        int *visited = new int[vertices];
        for (int i = 0; i < vertices; i++) visited[i] = 0;

        int *queue = new int[vertices];
        int front = 0, rear = 0;

        queue[rear++] = start;
        visited[start] = 1;

        while (front < rear) {
            int node = queue[front++];
            cout << node << " ";

            for (int i = 0; i < vertices; i++) {
                if (adjMatrix[node][i] == 1 && !visited[i]) {
                    queue[rear++] = i;
                    visited[i] = 1;
                }
            }
        }

        delete[] visited;
        delete[] queue;
    }

    void startDFS(int start) {
        int *visited = new int[vertices];
        for (int i = 0; i < vertices; i++) visited[i] = 0;

        cout << "DFS Traversal: ";
        dfs(start, visited);
        cout << endl;

        delete[] visited;
    }

    void startBFS(int start) {
        cout << "BFS Traversal: ";
        bfs(start);
        cout << endl;
    }

    void deleteGraph() {
        for (int i = 0; i < vertices; i++) {
            delete[] adjMatrix[i];
        }
        delete[] adjMatrix;
    }
};

int main() {
    Graph g;
    int v, e, start;
    cout << "Enter number of vertices: ";
    cin >> v;
    cout << "Enter number of edges: ";
    cin >> e;

    g.createGraph(v, e);

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

    g.startDFS(start);
    g.startBFS(start);
    g.deleteGraph();

    return 0;
}