Graph representation

Graph Representation | Adjacency Matrix vs Adjacency List

In computer science, a graph is a powerful data structure used to represent relationships, such as in social networks, maps, web links, and networking systems.

But how do we store a graph in memory?

There are two major methods:

• Adjacency Matrix

• Adjacency List

1. Adjacency Matrix Representation

What is it?

An adjacency matrix is a 2D array used to represent a graph.
Each row and column represents a vertex.
The value at position mat[i][j] shows whether there is an edge between vertex i and j.

• 0 means no edge

• 1 (or weight) means edge exists

Best for:

• Dense graphs (many connections)

• Faster edge lookup (O(1))

C Code Example:

#include <stdio.h>

#define V 4  // Number of vertices

void addEdge(int mat[V][V], int i, int j) {

    mat[i][j] = 1;

    mat[j][i] = 1; // For undirected graph

}

void displayMatrix(int mat[V][V]) {

    for (int i = 0; i < V; i++) {

        for (int j = 0; j < V; j++)

            printf("%d ", mat[i][j]);

        printf("\n");

    }

}

int main() {

    int mat[V][V] = {0};

    addEdge(mat, 0, 1);

    addEdge(mat, 0, 2);

    addEdge(mat, 1, 2);

    addEdge(mat, 2, 3);

    printf("Adjacency Matrix Representation\n");

    displayMatrix(mat);

    return 0;

}

Output:

Adjacency Matrix Representation  

0   1   1   0  

1.  0   1   0  

1   1   0   1  

0   0  1   0  

Each 1 shows a connection between the corresponding nodes.

2. Adjacency List Representation

What is it?

An adjacency list stores the graph using an array of linked lists.
Each index of the array represents a vertex. The linked list at that index holds all connected vertices.

Best for:

• Sparse graphs (fewer edges)

• Saves memory

C Code Example:

#include <stdio.h>

#include <stdlib.h>

struct Node {

    int data;

    struct Node* next;

};

struct Node* createNode(int data) {

    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

    newNode->data = data;

    newNode->next = NULL;

    return newNode;

}

void addEdge(struct Node* adj[], int i, int j) {

    struct Node* newNode = createNode(j);

    newNode->next = adj[i];

    adj[i] = newNode;

    newNode = createNode(i); // For undirected graph

    newNode->next = adj[j];

    adj[j] = newNode;

}

void displayAdjList(struct Node* adj[], int V) {

    for (int i = 0; i < V; i++) {

        printf("%d: ", i);

        struct Node* temp = adj[i];

        while (temp != NULL) {

            printf("%d ", temp->data);

            temp = temp->next;

        }

        printf("\n");

    }

}

int main() {

    int V = 4;

    struct Node* adj[V];

    for (int i = 0; i < V; i++)

        adj[i] = NULL;

    addEdge(adj, 0, 1);

    addEdge(adj, 0, 2);

    addEdge(adj, 1, 2);

    addEdge(adj, 2, 3);

    printf("Adjacency List Representation:\n");

    displayAdjList(adj, V);

    return 0;

}

Output:

Adjacency List Representation:  

0: 2  1  

1: 2  0  

2: 3  1  0  

3: 2  

Each line shows the connections from a vertex to others.

Comparison: Adjacency Matrix vs Adjacency List

Final Thought:

Understanding graph representations is crucial for implementing graph algorithms like DFS, BFS, Dijkstra, Prim's, and more.

• Use Adjacency Matrix when space isn’t a problem and speed is key.

• Use Adjacency List for memory efficiency in large sparse graphs.