8. Write a C program that dynamically allocates memory for a graph data structure and implements functions to add vertices and edges.

							
#include<stdio.h>
#include<stdlib.h>
// Structure for an adjacency list node
struct AdjListNode {
    int dest;
    struct AdjListNode* next;
};

// Structure for adjacency list of each vertex
struct AdjList {
    struct AdjListNode *head;
};

// Structure for a graph
struct Graph {
    int V;  // Number of vertices
    struct AdjList* array;
};

// Function to create a new adjacency list node
struct AdjListNode* newAdjListNode(int dest) {
    struct AdjListNode* newNode = (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
    if (!newNode) {
        printf("Memory allocation failed.\n");
        exit(1);
    }
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// Function to create a graph of V vertices
struct Graph* createGraph(int V) {
    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
    if (!graph) {
        printf("Memory allocation failed.\n");
        exit(1);
    }
    graph->V = V;

    // Create an array of adjacency lists
    graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));
    if (!graph->array) {
        printf("Memory allocation failed.\n");
        exit(1);
    }

    // Initialize each adjacency list as empty by making head as NULL
    for (int i = 0; i < V; ++i)
        graph->array[i].head = NULL;

    return graph;
}

// Function to add an edge to an undirected graph
void addEdge(struct Graph* graph, int src, int dest) {
    // Add an edge from src to dest
    struct AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    // Since the graph is undirected, add an edge from dest to src also
    newNode = newAdjListNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

// Function to print the graph
void printGraph(struct Graph* graph) {
    for (int v = 0; v < graph->V; ++v) {
        struct AdjListNode* temp = graph->array[v].head;
        printf("Adjacency list of vertex %d\n", v);
        while (temp) {
            printf(" -> %d", temp->dest);
            temp = temp->next;
        }
        printf("\n");
    }
}

// Function to free graph memory
void freeGraph(struct Graph* graph) {
    if (graph) {
        if (graph->array) {
            for (int v = 0; v < graph->V; ++v) {
                struct AdjListNode* temp = graph->array[v].head;
                while (temp) {
                    struct AdjListNode* prev = temp;
                    temp = temp->next;
                    free(prev);
                }
            }
            free(graph->array);
        }
        free(graph);
    }
}

// Main function to demonstrate graph operations
int main() {
    int V, E;
    printf("Enter the number of vertices in the graph: ");
    scanf("%d", &V);

    struct Graph* graph = createGraph(V);

    printf("Enter the number of edges in the graph: ");
    scanf("%d", &E);

    printf("Enter the edges (src dest):\n");
    for (int i = 0; i < E; ++i) {
        int src, dest;
        scanf("%d %d", &src, &dest);
        addEdge(graph, src, dest);
    }

    printf("Graph created successfully!\n");
    printf("Here is the adjacency list representation of the graph:\n");
    printGraph(graph);

    // Free dynamically allocated memory
    freeGraph(graph);

    return 0;
}