Overview

This document contains a C program that implements graph representation using both adjacency list and adjacency matrix. The program provides functionalities to add edges, display the graph, and perform basic operations.

Program Structure

The program is structured as follows:

• Definitions: Structures for the adjacency list and matrix representation.
• Functions: Functions to initialize the graph, add edges, display the graph, and cleanup.
• Main Function: Entry point of the program to demonstrate the functionality.

Code

#include 
#include 

#define MAX_VERTICES 100

// Structure for adjacency list node
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

// Structure for graph using adjacency list
typedef struct GraphList {
    int numVertices;
    Node** adjLists;
} GraphList;

// Structure for graph using adjacency matrix
typedef struct GraphMatrix {
    int numVertices;
    int** adjMatrix;
} GraphMatrix;

// Function prototypes
GraphList* createGraphList(int vertices);
GraphMatrix* createGraphMatrix(int vertices);
void addEdgeList(GraphList* graph, int src, int dest);
void addEdgeMatrix(GraphMatrix* graph, int src, int dest);
void displayGraphList(GraphList* graph);
void displayGraphMatrix(GraphMatrix* graph);
void freeGraphList(GraphList* graph);
void freeGraphMatrix(GraphMatrix* graph);

int main() {
    // Create a graph using adjacency list
    GraphList* graphList = createGraphList(5);
    addEdgeList(graphList, 0, 1);
    addEdgeList(graphList, 0, 4);
    addEdgeList(graphList, 1, 2);
    addEdgeList(graphList, 1, 3);
    addEdgeList(graphList, 1, 4);
    addEdgeList(graphList, 2, 3);
    addEdgeList(graphList, 3, 4);

    printf("Adjacency List Representation:\n");
    displayGraphList(graphList);
    freeGraphList(graphList);

    // Create a graph using adjacency matrix
    GraphMatrix* graphMatrix = createGraphMatrix(5);
    addEdgeMatrix(graphMatrix, 0, 1);
    addEdgeMatrix(graphMatrix, 0, 4);
    addEdgeMatrix(graphMatrix, 1, 2);
    addEdgeMatrix(graphMatrix, 1, 3);
    addEdgeMatrix(graphMatrix, 1, 4);
    addEdgeMatrix(graphMatrix, 2, 3);
    addEdgeMatrix(graphMatrix, 3, 4);

    printf("\nAdjacency Matrix Representation:\n");
    displayGraphMatrix(graphMatrix);
    freeGraphMatrix(graphMatrix);

    return 0;
}

// Create a graph using adjacency list
GraphList* createGraphList(int vertices) {
    GraphList* graph = malloc(sizeof(GraphList));
    graph->numVertices = vertices;
    graph->adjLists = malloc(vertices * sizeof(Node*));

    for (int i = 0; i < vertices; i++) { graph->adjLists[i] = NULL;
    }

    return graph;
}

// Create a graph using adjacency matrix
GraphMatrix* createGraphMatrix(int vertices) {
    GraphMatrix* graph = malloc(sizeof(GraphMatrix));
    graph->numVertices = vertices;
    graph->adjMatrix = malloc(vertices * sizeof(int*));

    for (int i = 0; i < vertices; i++) { graph->adjMatrix[i] = malloc(vertices * sizeof(int));
        for (int j = 0; j < vertices; j++) { graph->adjMatrix[i][j] = 0; // Initialize with 0
        }
    }

    return graph;
}

// Add edge to adjacency list
void addEdgeList(GraphList* graph, int src, int dest) {
    Node* newNode = malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // For undirected graph, add edge in both directions
    newNode = malloc(sizeof(Node));
    newNode->vertex = src;
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

// Add edge to adjacency matrix
void addEdgeMatrix(GraphMatrix* graph, int src, int dest) {
    graph->adjMatrix[src][dest] = 1;
    graph->adjMatrix[dest][src] = 1; // For undirected graph
}

// Display graph using adjacency list
void displayGraphList(GraphList* graph) {
    for (int i = 0; i < graph->numVertices; i++) {
        Node* temp = graph->adjLists[i];
        printf("Vertex %d: ", i);
        while (temp) {
            printf("-> %d ", temp->vertex);
            temp = temp->next;
        }
        printf("\n");
    }
}

// Display graph using adjacency matrix
void displayGraphMatrix(GraphMatrix* graph) {
    for (int i = 0; i < graph->numVertices; i++) {
        for (int j = 0; j < graph->numVertices; j++) {
            printf("%d ", graph->adjMatrix[i][j]);
        }
        printf("\n");
    }
}

// Free memory for adjacency list
void freeGraphList(GraphList* graph) {
    for (int i = 0; i < graph->numVertices; i++) {
        Node* temp = graph->adjLists[i];
        while (temp) {
            Node* toFree = temp;
            temp = temp->next;
            free(toFree);
        }
    }
    free(graph->adjLists);
    free(graph);
}

// Free memory for adjacency matrix
void freeGraphMatrix(GraphMatrix* graph) {
    for (int i = 0; i < graph->numVertices; i++) {
        free(graph->adjMatrix[i]);
    }
    free(graph->adjMatrix);
    free(graph);
}

Explanation of Key Functions

createGraphList(int vertices)

Allocates memory for the adjacency list representation of the graph and initializes it.

createGraphMatrix(int vertices)

Allocates memory for the adjacency matrix representation of the graph and initializes it to zero.

addEdgeList(GraphList* graph, int src, int dest)

Adds an edge between the source and destination vertices in the adjacency list. For undirected graphs, it adds the edge in both directions.

addEdgeMatrix(GraphMatrix* graph, int src, int dest)

Adds an edge between the source and destination vertices in the adjacency matrix.

displayGraphList(GraphList* graph)

Displays the adjacency list representation of the graph.

displayGraphMatrix(GraphMatrix* graph)

Displays the adjacency matrix representation of the graph.

freeGraphList(GraphList* graph)

Frees the memory allocated for the adjacency list representation of the graph.

freeGraphMatrix(GraphMatrix* graph)

Frees the memory allocated for the adjacency matrix representation of the graph.

Conclusion

This program provides a basic implementation of graph representation using both adjacency list and adjacency matrix. The choice between the two depends on the specific needs and constraints of the application.