Write a program to print adjacency matrix.

Adjacency Matrix

Adjacency matrix is a topic that comes under graph theory. Graph theory is a subject of study of graphs in discrete mathematics. Graphs are mathematical structures used to denote pairwise relations between objects. A graph is made up of vertices (nodes or points) that are connected by edges (links or lines).

An adjacency matrix is a finite graph and is often represented by a square matrix. Adjacency is the term which means next to something or adjoining something to. The elements of the matrix indicate whether pairs of vertices are adjacent or not or simply they are connected to each other or not.

An adjacency matrix is formed in a square matrix. Programming languages can represent a square matrix by 2D array. Here this array is a square of n x n array of number 1 or 0. In the array, the value of an element array[x,y] says node X is connected to Y or not. This array will have another diagonal mirror element array[y,x]. The value of array[x,y] says node Y is connected to X or not. There are two types of connection orientation possible here between these two nodes. They can be connected in both directions or they can be unidirectional.

Directed Graph

Directed graph consider the direction of the connection between two nodes. Below is a diagram shows a directed graph. Here node 1 and 2 connected by a directed connection and the direction is from node 1 to node 2. Node 1 can reach to node 2 but reverse is not possible.

Directed Graph

Undirected Graph

Undirected graph does not consider the direction of the connection between two nodes. Below is a diagram shows an undirected graph. We have converted previous directed graph to an undirected one. Now node 1 and node 2 can reach to each other by any direction.

Undirected Graph

Adjacency Matrix in C

Adjacency Matrix is a mathematical representation of a directed/undirected graph. It is a matrix of the order N x N where N is the total number of nodes present in the graph. In computer programming 2D array of integers are considered. All the elements e[x][y] are zero at initial stage. Zero represents no connection between x to y. We set the element e[x][y] to on when there is a directed connection from x to y. Undirected connection has both direction set to one. Thus we set e[x][y] = 1 and e[y][x] = 1 for any undirected connection.

#include <stdio.h>
int main(int argc, char* argv[])
{
  int **adj_matrix;
  char d;
  int r, c, nodes;
  printf ("== Adjacency Matrix Demo ==\n");
  printf ("Number of Nodes : ");
  scanf ("%d", &nodes);

  /* Dynamic allocation of matrix array */
  adj_matrix = (int **) malloc (sizeof(int **)*nodes);
  if(!adj_matrix) {
    printf ("Fatal error in memory allocation!");
    return -1;
  }
  for (r = 0; r < nodes; r++) {
    adj_matrix[r] = (int *) malloc(sizeof(int)*nodes);
    if(!adj_matrix[r]) {
      printf ("Fatal error in memory allocation!");
      return -1;
    }
  }
  for (r = 0; r < nodes; r++) {
    for (c = 0; c < nodes; c++) {
        adj_matrix[r][c] = 0;
    }

  }
  r = 0;
  c = 0;
  printf ("Node pair format <U/D> <V1> <V2>\n");
  do {
    printf ("Enter Node Pair : ");
    fflush(stdin);
    scanf ("%c %d %d", &d, &r, &c);
    if (r > 0 && r <= nodes && c > 0 && c <= nodes){
            adj_matrix[r - 1][c - 1] = 1;
      if(d == 'U' || d == 'u'){
      adj_matrix[c - 1][r - 1] = 1;
      printf ("Undirected connection between %d to %d\n", r, c);
      } else {
            printf ("Directed connection from %d to %d\n", r, c);
      }
    }
  }while(r > 0 && c > 0);

  printf("\nAdjacency matrix\n");
  printf(" ");
  for (c = 0; c < nodes; c++) {
    printf("%.1d ", c + 1);
  }
  printf("\n");
  for (c = 0; c < nodes; c++) {
    printf("---");
  }
  printf("\n");
  for (r = 0; r < nodes; r++) {
    printf("%.1d| ", r+1);
    for (c = 0; c < nodes; c++) {
        printf("%.1d ", adj_matrix[r][c]);
    }
    printf("\n");
  }
  return 0;
}

Adjacency matrix of Directed Graph

We set element[x][y] to 1 when there is a directed connection present between node x to y. Now this matrix may not be diagonally symmetric as element[y][x] may not be 1. Below is the output of our program

Directed Graph

Directed Graph in C

== Adjacency Matrix Demo ==
Number of Nodes : 5
Node pair format <U/D> <V1> <V2>
Enter Node Pair : D 1 2
Directed connection from 1 to 2
Enter Node Pair : D 1 3
Directed connection from 1 to 3
Enter Node Pair : D 2 3
Directed connection from 2 to 3
Enter Node Pair : D 2 4
Directed connection from 2 to 4
Enter Node Pair : D 4 5
Directed connection from 4 to 5
Enter Node Pair : D 5 3
Directed connection from 5 to 3
Enter Node Pair : D 3 3
Directed connection from 3 to 3
Enter Node Pair : D -1 -1

Adjacency matrix
   1 2 3 4 5
---------------
1| 0 1 1 0 0
2| 0 0 1 1 0
3| 0 0 1 0 0
4| 0 0 0 0 1
5| 0 0 1 0 0

Adjacency matrix of Undirected Graph

We set element[x][y] and element[y][x] to 1 when there is an undirected connection present between node x to y. Now this matrix is perfectly diagonally symmetric. Below is the output of our program.

Undirected Graph

Undirected Graph in C

== Adjacency Matrix Demo ==
Number of Nodes : 5
Node pair format <U/D> <V1> <V2>
Enter Node Pair : U 1 2
Undirected connection between 1 to 2
Enter Node Pair : U 1 3
Undirected connection between 1 to 3
Enter Node Pair : U 2 3
Undirected connection between 2 to 3
Enter Node Pair : U 3 3
Undirected connection between 3 to 3
Enter Node Pair : U 2 4
Undirected connection between 2 to 4
Enter Node Pair : U 3 5
Undirected connection between 3 to 5
Enter Node Pair : U 4 5
Undirected connection between 4 to 5
Enter Node Pair : D -1 -1

Adjacency matrix
   1 2 3 4 5
---------------
1| 0 1 1 0 0
2| 1 0 1 1 0
3| 1 1 1 0 1
4| 0 1 0 0 1
5| 0 0 1 1 0

About our authors: Team EQA

You have viewed 1 page out of 252. Your C learning is 0.00% complete. Login to check your learning progress.

‹ # ›

Questions index C Questions C++ Questions Win32 MFC COM/DCOM DLL Questions