Graph Data Structures

1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5// Define the maximum number of vertices
6#define MAX_VERTICES 100
7
8// Graph represented as an adjacency list
9typedef struct {
10    int vertices;                // Number of vertices
11    int* adjacencyList[MAX_VERTICES]; // Array of adjacency lists
12    int size[MAX_VERTICES];      // Size of each adjacency list
13    int capacity[MAX_VERTICES];  // Capacity of each adjacency list
14} Graph;
15
16// Initialize a graph with n vertices
17Graph* createGraph(int vertices) {
18    Graph* graph = (Graph*)malloc(sizeof(Graph));
19    graph->vertices = vertices;
20    
21    for (int i = 0; i < vertices; i++) {
22        graph->adjacencyList[i] = (int*)malloc(sizeof(int));
23        graph->size[i] = 0;
24        graph->capacity[i] = 1;
25    }
26    
27    return graph;
28}
29
30// Add an edge to the graph (for undirected graph)
31void addEdge(Graph* graph, int src, int dest) {
32    // Add edge from src to dest
33    if (graph->size[src] == graph->capacity[src]) {
34        graph->capacity[src] *= 2;
35        graph->adjacencyList[src] = (int*)realloc(graph->adjacencyList[src], graph->capacity[src] * sizeof(int));
36    }
37    graph->adjacencyList[src][graph->size[src]++] = dest;
38    
39    // Add edge from dest to src (for undirected graph)
40    if (graph->size[dest] == graph->capacity[dest]) {
41        graph->capacity[dest] *= 2;
42        graph->adjacencyList[dest] = (int*)realloc(graph->adjacencyList[dest], graph->capacity[dest] * sizeof(int));
43    }
44    graph->adjacencyList[dest][graph->size[dest]++] = src;
45}
46
47// Print the adjacency list representation of the graph
48void printGraph(Graph* graph) {
49    for (int i = 0; i < graph->vertices; i++) {
50        printf("Adjacency list of vertex %d: ", i);
51        for (int j = 0; j < graph->size[i]; j++) {
52            printf("%d -> ", graph->adjacencyList[i][j]);
53        }
54        printf("NULL\n");
55    }
56}
57
58// Free the memory allocated for the graph
59void freeGraph(Graph* graph) {
60    for (int i = 0; i < graph->vertices; i++) {
61        free(graph->adjacencyList[i]);
62    }
63    free(graph);
64}
65
66// Driver program
67int main() {
68    // Create a graph with 5 vertices (labeled 0 to 4)
69    Graph* graph = createGraph(5);
70    
71    // Add edges to the graph
72    addEdge(graph, 0, 1); // A - B
73    addEdge(graph, 0, 2); // A - C
74    addEdge(graph, 1, 2); // B - C
75    addEdge(graph, 1, 3); // B - D
76    addEdge(graph, 2, 4); // C - E
77    addEdge(graph, 3, 4); // D - E
78    
79    // Print the adjacency list representation
80    printGraph(graph);
81    
82    // Free allocated memory
83    freeGraph(graph);
84    
85    return 0;
86}