dfdbfsadjlist.cpp

#include <iostream>
using namespace std;

class Graph {
    int vertices;
    int **adjList; // Adjacency list (dynamic array of pointers)
    int *sizes; // Array to store the number of neighbors for each vertex

public:
    Graph(int v) {
        vertices = v;
        adjList = new int*[vertices]; // Array of pointers
        sizes = new int[vertices]; // Array to track number of neighbors

        for (int i = 0; i < vertices; i++) {
            adjList[i] = nullptr; // Initially, no neighbors
            sizes[i] = 0;
        }
    }

    void addEdge(int u, int v) {
        sizes[u]++;
        sizes[v]++;

        int *tempU = new int[sizes[u]];
        int *tempV = new int[sizes[v]];

        for (int i = 0; i < sizes[u] - 1; i++) tempU[i] = adjList[u][i];
        for (int i = 0; i < sizes[v] - 1; i++) tempV[i] = adjList[v][i];

        tempU[sizes[u] - 1] = v;
        tempV[sizes[v] - 1] = u;

        delete[] adjList[u];
        delete[] adjList[v];

        adjList[u] = tempU;
        adjList[v] = tempV;
    }

    void deleteEdge(int u, int v) {
        int newSizeU = 0, newSizeV = 0;

        for (int i = 0; i < sizes[u]; i++) if (adjList[u][i] != v) newSizeU++;
        for (int i = 0; i < sizes[v]; i++) if (adjList[v][i] != u) newSizeV++;

        int *tempU = newSizeU > 0 ? new int[newSizeU] : nullptr;
        int *tempV = newSizeV > 0 ? new int[newSizeV] : nullptr;

        int indexU = 0, indexV = 0;
        for (int i = 0; i < sizes[u]; i++) if (adjList[u][i] != v) tempU[indexU++] = adjList[u][i];
        for (int i = 0; i < sizes[v]; i++) if (adjList[v][i] != u) tempV[indexV++] = adjList[v][i];

        delete[] adjList[u];
        delete[] adjList[v];

        adjList[u] = tempU;
        adjList[v] = tempV;

        sizes[u] = newSizeU;
        sizes[v] = newSizeV;
    }

    void printGraph() {
        cout << "Adjacency List:\n";
        for (int i = 0; i < vertices; i++) {
            cout << i << " -> ";
            for (int j = 0; j < sizes[i]; j++) {
                cout << adjList[i][j] << " ";
            }
            cout << endl;
        }
    }

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

        stack[++top] = start;
        visited[start] = 1;

        cout << "DFS Traversal: ";

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

            for (int i = sizes[node] - 1; i >= 0; i--) {
                int neighbor = adjList[node][i];
                if (!visited[neighbor]) {
                    stack[++top] = neighbor;
                    visited[neighbor] = 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;

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

        cout << "BFS Traversal: ";

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

            for (int i = 0; i < sizes[node]; i++) {
                int neighbor = adjList[node][i];
                if (!visited[neighbor]) {
                    queue[rear++] = neighbor;
                    visited[neighbor] = 1;
                }
            }
        }
        cout << endl;

        delete[] queue;
        delete[] visited;
    }

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

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 << "Graph before deleting an edge:" << endl;
    g.printGraph();

    cout << "Enter an edge to delete (u v): ";
    cin >> u >> v;
    g.deleteEdge(u, v);

    cout << "Graph after deleting the edge:" << endl;
    g.printGraph();

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

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

    return 0;
}