graphrepres.cpp

#include <iostream>
using namespace std;

class Graph {
private:
    int vertices;       // Number of vertices
    int** adjMatrix;    // Adjacency matrix
    struct Node {
        int vertex;
        Node* next;
    };
    Node** adjList;     // Adjacency list (array of linked lists)

public:
    // Constructor
    Graph(int v) {
        vertices = v;

        // Initialize adjacency matrix
        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; // Initialize all values to 0
            }
        }

        // Initialize adjacency list
        adjList = new Node*[vertices];
        for (int i = 0; i < vertices; i++) {
            adjList[i] = nullptr; // Start with empty linked lists
        }
    }

    // Add an edge (undirected graph)
    void addEdge(int u, int v) {
        // Update adjacency matrix
        adjMatrix[u][v] = 1;
        adjMatrix[v][u] = 1; // For undirected graph

        // Update adjacency list
        Node* newNode1 = new Node{v, adjList[u]};
        adjList[u] = newNode1;

        Node* newNode2 = new Node{u, adjList[v]};
        adjList[v] = newNode2;
    }

    // Display adjacency matrix
    void displayAdjMatrix() {
        cout << "Adjacency Matrix:\n";
        for (int i = 0; i < vertices; i++) {
            for (int j = 0; j < vertices; j++) {
                cout << adjMatrix[i][j] << " ";
            }
            cout << endl;
        }
    }

    // Display adjacency list
    void displayAdjList() {
        cout << "Adjacency List:\n";
        for (int i = 0; i < vertices; i++) {
            cout << i << ": ";
            Node* temp = adjList[i];
            while (temp != nullptr) {
                cout << temp->vertex << " ";
                temp = temp->next;
            }
            cout << endl;
        }
    }

    // Destructor to free memory
    ~Graph() {
        // Free adjacency matrix
        for (int i = 0; i < vertices; i++) {
            delete[] adjMatrix[i];
        }
        delete[] adjMatrix;

        // Free adjacency list
        for (int i = 0; i < vertices; i++) {
            Node* temp = adjList[i];
            while (temp != nullptr) {
                Node* toDelete = temp;
                temp = temp->next;
                delete toDelete;
            }
        }
        delete[] adjList;
    }
};

int main() {
    int vertices, edges;

    cout << "Enter the number of vertices: ";
    cin >> vertices;

    Graph graph(vertices);

    cout << "Enter the number of edges: ";
    cin >> edges;

    cout << "Enter the edges (u v):\n";
    for (int i = 0; i < edges; i++) {
        int u, v;
        cin >> u >> v;
        graph.addEdge(u, v);
    }

    // Display adjacency matrix and list
    graph.displayAdjMatrix();
    graph.displayAdjList();

    return 0;
}