Graph Representation Methods

After understanding what a graph is and its various types, the next crucial question is: How do we store a graph in a computer's memory?

The choice of representation significantly impacts the performance of graph algorithms, especially when dealing with large networks. In this post, we'll explore the two most fundamental graph representation methods: Adjacency Matrix and Adjacency List.

Why Representation Matters?

• Memory Efficiency: Different representations use different amounts of memory.
• Time Efficiency: Certain operations (like checking if an edge exists) are faster with one representation over another.
• Algorithm Suitability: Some algorithms work better with specific representations.

1. Adjacency Matrix

An adjacency matrix is a 2D array of size V × V where V is the number of vertices. The entry matrix[i][j] indicates whether there is an edge between vertex i and vertex j.

Rules for Populating the Matrix

• Undirected Graph: matrix[i][j] = 1 if there is an edge between i and j, else 0. The matrix is symmetric (matrix[i][j] == matrix[j][i]).
• Directed Graph: matrix[i][j] = 1 if there is an edge from i to j, else 0. The matrix is not necessarily symmetric.
• Weighted Graph: Store the weight instead of 1 (and 0 or ∞ for no edge).

Example: Undirected Graph

Consider the following undirected graph:

A — B
|   |
C — D

Vertices: A, B, C, D (indices 0, 1, 2, 3)

Adjacency Matrix:

    A  B  C  D
A   0  1  1  0
B   1  0  0  1
C   1  0  0  1
D   0  1  1  0

Example: Directed Graph

Consider the following directed graph:

A → B
↓   ↑
C → D

Adjacency Matrix:

    A  B  C  D
A   0  1  1  0
B   0  0  0  1
C   0  0  0  1
D   0  0  0  0

Advantages

1. Fast Edge Lookup: Checking if an edge exists between i and j is O(1) – just check matrix[i][j].
2. Simple Implementation: Straightforward to implement with a 2D array.
3. Good for Dense Graphs: When E (edges) is close to V², the matrix is memory-efficient compared to adjacency lists.

Disadvantages

1. High Memory Usage: Requires O(V²) space, even for sparse graphs (where E is much less than V²).
2. Expensive Traversal: Finding all neighbors of a vertex requires iterating through an entire row (O(V) time).

2. Adjacency List

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

Representation

• For each vertex i, we store a list of its neighbors.
• For weighted graphs, we store pairs (neighbor, weight).

Example: Undirected Graph (Same as above)

Vertices: A, B, C, D

Adjacency List:

A: B → C → NULL
B: A → D → NULL
C: A → D → NULL
D: B → C → NULL

Example: Directed Graph (Same as above)

Adjacency List:

A: B → C → NULL
B: D → NULL
C: D → NULL
D: NULL

Advantages

1. Memory Efficient for Sparse Graphs: Uses O(V + E) space, much better than O(V²).
2. Efficient Traversal: Finding all neighbors of a vertex is O(degree) – you just traverse its list.
3. Flexible: Easy to add or remove vertices.

Disadvantages

1. Slower Edge Lookup: Checking if an edge exists between i and j requires searching through the list of i (O(degree) time).
2. Slightly More Complex: Requires implementing linked lists or dynamic arrays.

Comparison of Representation Methods

Implementation in C

Adjacency Matrix Implementation

#include <stdio.h>
#include <stdlib.h>
#define MAX 10

int adjMatrix[MAX][MAX];
int vertices;

// Initialize the matrix with 0 (no edges)
void initMatrix(int v) {
    vertices = v;
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            adjMatrix[i][j] = 0;
        }
    }
}

// Add edge (undirected)
void addEdge(int u, int v) {
    if (u >= vertices || v >= vertices) {
        printf("Invalid vertex!\n");
        return;
    }
    adjMatrix[u][v] = 1;
    adjMatrix[v][u] = 1;  // For undirected graph
}

// Display the matrix
void displayMatrix() {
    printf("\nAdjacency Matrix:\n   ");
    for (int i = 0; i < vertices; i++) {
        printf("%c ", 'A' + i);
    }
    printf("\n");
    for (int i = 0; i < vertices; i++) {
        printf("%c  ", 'A' + i);
        for (int j = 0; j < vertices; j++) {
            printf("%d ", adjMatrix[i][j]);
        }
        printf("\n");
    }
}

int main() {
    initMatrix(4);
    addEdge(0, 1); // A-B
    addEdge(0, 2); // A-C
    addEdge(1, 3); // B-D
    addEdge(2, 3); // C-D
    displayMatrix();
    return 0;
}

Output:

Adjacency Matrix:
   A B C D
A  0 1 1 0
B  1 0 0 1
C  1 0 0 1
D  0 1 1 0

Adjacency List Implementation

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

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

// Graph structure
typedef struct Graph {
    int vertices;
    Node** adjLists;
} Graph;

// Create a node
Node* createNode(int v) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// Create a graph
Graph* createGraph(int v) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->vertices = v;
    graph->adjLists = (Node**)malloc(v * sizeof(Node*));
    for (int i = 0; i < v; i++) {
        graph->adjLists[i] = NULL;
    }
    return graph;
}

// Add edge (undirected)
void addEdge(Graph* graph, int u, int v) {
    // Add v to u's list
    Node* newNode = createNode(v);
    newNode->next = graph->adjLists[u];
    graph->adjLists[u] = newNode;
    
    // Add u to v's list (for undirected graph)
    newNode = createNode(u);
    newNode->next = graph->adjLists[v];
    graph->adjLists[v] = newNode;
}

// Display the adjacency list
void displayList(Graph* graph) {
    printf("\nAdjacency List:\n");
    for (int i = 0; i < graph->vertices; i++) {
        printf("%c: ", 'A' + i);
        Node* temp = graph->adjLists[i];
        while (temp) {
            printf("%c → ", 'A' + temp->vertex);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    Graph* graph = createGraph(4);
    addEdge(graph, 0, 1); // A-B
    addEdge(graph, 0, 2); // A-C
    addEdge(graph, 1, 3); // B-D
    addEdge(graph, 2, 3); // C-D
    displayList(graph);
    return 0;
}

Output:

Adjacency List:
A: C → B → NULL
B: D → A → NULL
C: D → A → NULL
D: C → B → NULL

When to Use Which Representation?

Choose Adjacency Matrix When:

• The graph is dense (many edges).
• You need frequent edge existence checks (O(1)).
• The graph is small and memory isn't a concern.

Choose Adjacency List When:

• The graph is sparse (few edges).
• You need to traverse all neighbors frequently.
• Memory efficiency is important.
• The graph is dynamic (edges are added/removed frequently).