Mastering Graph Representation in C: Adjacency Matrix vs. Adjacency List

Graphs are fundamental non-linear data structures used to model various real-world problems, from social networks and road maps to circuit designs and task scheduling. In C programming, effectively representing a graph is the first crucial step before implementing any graph algorithm. This post dives deep into the two most common ways to represent graphs: the Adjacency Matrix and the Adjacency List, complete with C language implementations.

Understanding the trade-offs between these two representations—in terms of space complexity, time complexity for operations, and ease of implementation—is vital for developing efficient graph-based applications. Let's explore each method in detail.

1. Adjacency Matrix Representation

The adjacency matrix is a simple and intuitive way to represent a graph. It uses a 2D array (matrix) where the rows and columns represent the vertices (nodes) of the graph. A value in matrix[i][j] indicates the presence or absence of an edge between vertex i and vertex j.

Concept:

• For an unweighted graph, a value of 1 (or true) at matrix[i][j] means an edge exists from vertex i to vertex j. A value of 0 (or false) means no edge exists.
• For a weighted graph, matrix[i][j] can store the weight of the edge. A special value (e.g., 0 or infinity) can denote no edge.
• For an undirected graph, the matrix will be symmetric (matrix[i][j] = matrix[j][i]). For a directed graph, it may not be.

Advantages:

• Fast Edge Checking: Determining if an edge exists between two vertices takes O(1) time.
• Simplicity: Easy to implement, especially for dense graphs.

Disadvantages:

• Space Complexity: Requires O(V^2) space, where V is the number of vertices. This can be highly inefficient for sparse graphs (graphs with few edges).
• Iterating Neighbors: To find all neighbors of a vertex, you might need to iterate through an entire row/column, taking O(V) time.
• Adding/Removing Vertices: Costly, as it requires resizing and potentially copying the entire matrix.

C Implementation for Adjacency Matrix:

Here's a basic C implementation for an unweighted, undirected graph using an adjacency matrix.

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 100 // Maximum number of vertices

// Adjacency matrix representation
int adjMatrix[MAX_VERTICES][MAX_VERTICES];
int numVertices; // Current number of vertices in the graph

// Function to initialize the graph with V vertices
void initGraph(int vertices) {
    numVertices = vertices;
    for (int i = 0; i < numVertices; i++) {
        for (int j = 0; j < numVertices; j++) {
            adjMatrix[i][j] = 0; // Initialize all edges to 0 (no edge)
        }
    }
}

// Function to add an edge to the graph
// For an undirected graph, add edge from u to v and v to u
void addEdge(int u, int v) {
    if (u >= 0 && u < numVertices && v >= 0 && v < numVertices) {
        adjMatrix[u][v] = 1;
        adjMatrix[v][u] = 1; // For undirected graph
    } else {
        printf("Invalid vertices!\n");
    }
}

// Function to print the adjacency matrix
void printGraph() {
    printf("Adjacency Matrix:\n");
    for (int i = 0; i < numVertices; i++) {
        for (int j = 0; j < numVertices; j++) {
            printf("%d ", adjMatrix[i][j]);
        }
        printf("\n");
    }
}

// Main function to demonstrate
int main() {
    int vertices = 5; // Example: a graph with 5 vertices
    initGraph(vertices);

    addEdge(0, 1);
    addEdge(0, 4);
    addEdge(1, 2);
    addEdge(1, 3);
    addEdge(1, 4);
    addEdge(2, 3);
    addEdge(3, 4);

    printGraph();

    // Check if an edge exists
    printf("\nEdge between 0 and 1: %s\n", adjMatrix[0][1] ? "Yes" : "No");
    printf("Edge between 0 and 2: %s\n", adjMatrix[0][2] ? "Yes" : "No");

    return 0;
}

2. Adjacency List Representation

The adjacency list represents a graph as an array of linked lists. Each index in the array corresponds to a vertex, and the linked list at that index contains all the vertices adjacent to it.

Concept:

• For each vertex u, we store a list of vertices v such that there is an edge from u to v.
• For an unweighted graph, the list nodes simply contain the destination vertex.
• For a weighted graph, each list node can also store the weight of the edge.
• For an undirected graph, if there's an edge between u and v, then v will appear in u's list, and u will appear in v's list.

Advantages:

• Space Efficiency: Requires O(V + E) space, where V is the number of vertices and E is the number of edges. This is highly efficient for sparse graphs.
• Iterating Neighbors: Finding all neighbors of a vertex takes O(degree(V)) time, which is much faster than O(V) for sparse graphs.

Disadvantages:

• Slower Edge Checking: Checking if an edge exists between two specific vertices takes O(degree(V)) time in the worst case (as you need to traverse the linked list).
• More Complex: Implementation is slightly more complex due to dynamic memory allocation for linked lists.

C Implementation for Adjacency List:

Here's a basic C implementation for an unweighted, undirected graph using an adjacency list.

#include <stdio.h>
#include <stdlib.h>

// A structure to represent an adjacency list node
struct AdjListNode {
    int dest;
    struct AdjListNode* next;
};

// A structure to represent an adjacency list
struct AdjList {
    struct AdjListNode *head; // Pointer to the head node of the list
};

// A structure to represent a graph. A graph is an array of adjacency lists.
// Size of array will be V (number of vertices)
struct Graph {
    int numVertices;
    struct AdjList* array;
};

// Function to create a new adjacency list node
struct AdjListNode* createNode(int dest) {
    struct AdjListNode* newNode = (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// Function to create a graph with V vertices
struct Graph* createGraph(int vertices) {
    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
    graph->numVertices = vertices;

    // Create an array of adjacency lists. Size of array will be V
    graph->array = (struct AdjList*) malloc(vertices * sizeof(struct AdjList));

    // Initialize each adjacency list as empty by setting head to NULL
    for (int i = 0; i < vertices; 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. A new node is added to the adjacency list of src.
    // The node is added at the beginning for simplicity.
    struct AdjListNode* newNode = createNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

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

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

// Main function to demonstrate
int main() {
    int vertices = 5; // Example: a graph with 5 vertices
    struct Graph* graph = createGraph(vertices);

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    printGraph(graph);

    // Free allocated memory
    for (int i = 0; i < graph->numVertices; i++) {
        struct AdjListNode* current = graph->array[i].head;
        while (current != NULL) {
            struct AdjListNode* next = current->next;
            free(current);
            current = next;
        }
    }
    free(graph->array);
    free(graph);

    return 0;
}

3. Adjacency Matrix vs. Adjacency List: A Comparison

The choice between an adjacency matrix and an adjacency list primarily depends on the graph's characteristics (dense vs. sparse) and the operations you need to perform frequently.

When to Use Which:

• Adjacency Matrix: Prefer this for dense graphs, where the number of edges E is close to the maximum possible (V^2). It's also ideal when you frequently need to check if an edge exists between two specific vertices.
• Adjacency List: This is generally preferred for sparse graphs, where E is significantly smaller than V^2. It saves a lot of memory and is more efficient for algorithms that involve iterating over a vertex's neighbors (like Breadth-First Search or Depth-First Search).

Conclusion

Both adjacency matrix and adjacency list are powerful tools for representing graphs in C. The "best" choice is entirely contextual. By understanding their underlying mechanics, space/time complexities, and typical use cases, you can make an informed decision that will significantly impact the performance and memory footprint of your graph-based applications. Whether you're building a network router simulator or an AI pathfinding algorithm, choosing the right graph representation is a cornerstone of efficient design.