Home » Data Structure

Creation of adjacency matrix

In this article, we will learn about what adjacency matrix is and how it is created?
Submitted by Manu Jemini, on January 06, 2018

A graph is a set of nodes or known number of vertices. When these vertices are paired together, we call it edges. An Edge is a line from one node to other. Every edge can have its cost or weight.

Graphs are two types Directed and Undirected. Directed graphs are the graphs in which the vertices are ordered and in undirected graphs the vertices are unordered.

An Adjacency matrix is a finite set of values used to create an easy way to look for an edge. If the value at 0^th row and 1^st column are zero, it means the edge does not exist.

Image source: https://www.geeksforgeeks.org/wpcontent/uploads/adjacency_matrix_representation.png

In the example below, the program is made to create an adjacency matrix for either of Directed or Undirected type of graph.

The Program will ask for the number of nodes then the directed or undirected graph. After that it will ask for the values of the node. In the end, it will print the matrix.

The Adjacency matrix is the 2-D array of integers.

C program to create adjacency matrix

#include<stdio.h>
#define max 20

int adj[max][max]; /*Adjacency matrix */
int n;    /* Denotes number of nodes in the graph */
main()
{
	int max_edges,i,j,origin,destin;
	char graph_type;
	printf("Enter number of nodes : ");
	scanf("%d",&n);
	printf("Enter type of graph, directed or undirected (d/u) : ");
	fflush(stdin);
	scanf("%c",&graph_type);

	if(graph_type=='u')
		max_edges=n*(n-1)/2;
	else
		max_edges=n*(n-1);

	for(i=1;i<=max_edges;i++)
	{
		printf("Enter edge %d( 0 0 to quit ) : ",i);
		scanf("%d %d",&origin,&destin);
		if( (origin==0) && (destin==0) )
			break;
		if( origin > n || destin > n || origin<=0 || destin<=0)
		{
			printf("Invalid edge!\n");
			i--;
		}
		else
		{
			adj[origin][destin]=1;
			if( graph_type=='u')
				adj[destin][origin]=1;
		}
	}/*End of for*/

	printf("The adjacency matrix is :\n");
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
			printf("%4d",adj[i][j]);
		printf("\n");
	}
}/*End of main()*/

Output