Adjacency Matrix

In mathematics and computer science, an adjacency matrix is a means of representing which vertices (or nodes) of a graph are adjacent to which other vertices. Another matrix representation for a graph is the incidence matrix.

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 elements

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);
10 
11    /* Dynamic allocation of matrix array */
12    adj_matrix = (int **) malloc (sizeof(int **)*nodes);
13    if(!adj_matrix) {
14      printf ("Fatal error in memory allocation!");
15      return -1;
16    }
17    for (= 0; r < nodes; r++) {
18      adj_matrix[r] = (int *) malloc(sizeof(int)*nodes);
19      if(!adj_matrix[r]) {
20        printf ("Fatal error in memory allocation!");
21        return -1;
22      }
23    }
24    for (= 0; r < nodes; r++) {
25      for (= 0; c < nodes; c++) {
26          adj_matrix[r][c] = 0;
27      }
28 
29    }
30    r = 0;
31    c = 0;
32    printf ("Node pair format <U/D> <V1> <V2>\n");
33    do {
34      printf ("Enter Node Pair : ");
35      fflush(stdin);
36      scanf ("%c %d %d", &d, &r, &c);
37      if (> 0 && r <= nodes && c > 0 && c <= nodes){
38              adj_matrix[- 1][- 1] = 1;
39        if(== 'U' || d == 'u'){
40        adj_matrix[- 1][- 1] = 1;
41        printf ("Undirected connection between %d to %d\n", r, c);
42        } else {
43              printf ("Directed connection from %d to %d\n", r, c);
44        }
45      }
46    }while(> 0 && c > 0);
47 
48    printf("\nAdjacency matrix\n");
49    printf(" ");
50    for (= 0; c < nodes; c++) {
51      printf("%.1d ", c + 1);
52    }
53    printf("\n");
54    for (= 0; c < nodes; c++) {
55      printf("---");
56    }
57    printf("\n");
58    for (= 0; r < nodes; r++) {
59      printf("%.1d| ", r+1);
60      for (= 0; c < nodes; c++) {
61          printf("%.1d ", adj_matrix[r][c]);
62      }
63      printf("\n");
64    }
65    return 0;
66  }

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
== 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
== 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

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

 Vote 0

Similar topics related to this section

array, multidimensional arrays, 2D and 3D dynamic array, add Matrix, multiply Matrix, adjacency Matrix, Circular buffer, char array and char pointers,

# C Programming Language (Prentice Hall Software)
# Let Us C Paperback - 2006 by Yashavant Kanetkar
# Understanding and Using C Pointers Core techniques for memory management
# Data Structures Using C and C++ Paperback - 1998
# Data Structures In C Paperback - August 11, 2008 by Noel Kalicharan