C Programs

Share with a Friend

Data Structures in C

Graph Representation (Adjacency Matrix)

Let’s go step-by-step and then I’ll give you the complete C program.

What is a Graph?

A Graph is a non-linear data structure consisting of nodes (vertices) and edges that connect pairs of nodes.

It is represented as:

G = (V, E)
where V = set of vertices, and E = set of edges between vertices.

Graph Representation Methods

There are two main ways to represent graphs in memory:

       1. Adjacency Matrix

       2. Adjacency List

Here we’ll focus on the Adjacency Matrix representation.

Adjacency Matrix Representation

Definition

An Adjacency Matrix is a 2D array of size V x V where:

• V = number of vertices.
• Each cell adj[i][j] represents an edge from vertex i to vertex j.

Rules:

• For unweighted graphs:
• adj[i][j] = 1 if there is an edge from i to j.
• adj[i][j] = 0 otherwise.
• For weighted graphs, adj[i][j] = weight of the edge, and 0 (or INF) if no edge exists.

Example

Consider an undirected graph with 4 vertices and edges:

0 — 1

|   |

2 — 3

Adjacency Matrix:

C Program: Graph Representation using Adjacency Matrix

#include <stdio.h>
 
#define MAX_VERTICES 10
 
void displayMatrix(int adj[MAX_VERTICES][MAX_VERTICES], int vertices) {
    printf("\nAdjacency Matrix Representation:\n");
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            printf("%d ", adj[i][j]);
        }
        printf("\n");
    }
}
 
int main() {
    int vertices, edges;
    int adj[MAX_VERTICES][MAX_VERTICES] = {0};
 
    printf("Enter number of vertices: ");
    scanf("%d", &vertices);
 
    printf("Enter number of edges: ");
    scanf("%d", &edges);
 
    printf("\nEnter edges (u v):\n");
    for (int i = 0; i < edges; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
 
        // Since it's an undirected graph, mark both [u][v] and [v][u]
        adj[u][v] = 1;
        adj[v][u] = 1;
    }
 
    displayMatrix(adj, vertices);
 
    return 0;
}

 
INPUT :
Enter number of vertices: 4
Enter number of edges: 4
Enter edges (u v):
0 1
0 2
1 3
2 3

OUTPUT :
Adjacency Matrix Representation:
0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0

Complexity Analysis

• Very fast lookup, but space-heavy for large sparse graphs.

Key Takeaways

• Easy to implement and visualize.
• Best suited for dense graphs (many edges).
• Not memory-efficient for sparse graphs (few edges).
• Can be easily modified to support directed or weighted

Variations You Can Try

1. Directed Graph:
   Only mark adj[u][v] = 1 (not both ways).
2. Weighted Graph:
   Store edge weights instead of 1.
3. Self-loop support:
   Allow adj[i][i] = 1.