Adjacency Matrix Representation of Graph

We can easily represent the graphs using the following ways,

1. Adjacency matrix

2. Adjacency list

In this tutorial, we are going to see how to represent the graph using adjacency matrix.

Adjacency Matrix

If a graph has n vertices, we use n x n matrix to represent the graph.

Let's assume the n x n matrix as adj[n][n].

if there is an edge from vertex i to j, mark adj[i][j] as 1. i.e. adj[i][j] == 1

if there is no edge from vertex i to j, mark adj[i][j] as 0. i.e. adj[i][j] == 0

Undirected Graph

Adjacency Matrix of Undirected Graph

	0	1	2	3	4
0	0	1	1	1	0
1	1	0	0	1	1
2	1	0	0	1	0
3	1	1	1	0	1
4	0	1	0	1	0

Directed Graph

Adjacency Matrix of Directed Graph

	1	2	3	4
0	1	1	1	0
1	0	0	1	1
2	0	0	1	0
3	0	0	0	1
4	0	0	0	0

C Program to Implement Adjacency Matrix

Example

/*
 * Program  : Adjacency Matrix Representation of Graph
 * Language : C
 */
#include<stdio.h>
#define V 5

//init matrix to 0
void init(int arr[][V])
{
    int i,j;
    for(i = 0; i < V; i++)
        for(j = 0; j < V; j++)
            arr[i][j] = 0;
}

//Add edge. set arr[src][dest] = 1
void addEdge(int arr[][V],int src, int dest)
{
     arr[src][dest] = 1;
}

void printAdjMatrix(int arr[][V])
{
     int i, j;

     for(i = 0; i < V; i++)
     {
         for(j = 0; j < V; j++)
         {
             printf("%d ", arr[i][j]);
         }
         printf("\n");
     }
}

//print the adjMatrix
int main()
{
    int adjMatrix[V][V];

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

    printAdjMatrix(adjMatrix);

    return 0;
}