bfsdfs.cpp

#include <iostream>
using namespace std;

class Graph {
    int **adjMatrix;
    int vertices;

public:
    Graph(int v) {
        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;
            }
        }
    }

    void addEdge(int u, int v) {
        adjMatrix[u][v] = 1;
        adjMatrix[v][u] = 1; 
    }

    void DFS(int start) {
        int *stack = new int[vertices];
        int *visited = new int[vertices];
        int top = -1;

        for (int i = 0; i < vertices; i++) {
            visited[i] = 0;
        }

        stack[++top] = start;
        visited[start] = 1;
        cout << "DFS Traversal: ";

        while (top != -1) {
            int node = stack[top--];
            cout << node << " ";

            for (int i = vertices - 1; i >= 0; i--) {
                if (adjMatrix[node][i] == 1 && visited[i] == 0) {
                    stack[++top] = i;
                    visited[i] = 1;
                }
            }
        }
        cout << endl;
        delete[] stack;
        delete[] visited;
    }

    void BFS(int start) {
        int *queue = new int[vertices];
        int *visited = new int[vertices];
        int front = 0, rear = 0;

        for (int i = 0; i < vertices; i++) {
            visited[i] = 0;
        }

        queue[rear++] = start;
        visited[start] = 1;
        cout << "BFS Traversal: ";

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

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

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

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

    cout << "Enter number of edges: ";
    cin >> edges;
    cout << "Enter edges (u v):" << endl;
    for (int i = 0; i < edges; i++) {
        cin >> u >> v;
        g.addEdge(u, v);
    }

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

    g.DFS(start);
    g.BFS(start);

    return 0;
}