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.

## 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.

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.

``` 1  #include <stdio.h>
2  int main(int argc, char* argv[])
3  {
5    char d;
6    int r, c, nodes;
7    printf ("== Adjacency Matrix Demo ==\n");
8    printf ("Number of Nodes : ");
9    scanf ("%d", &nodes);
10
11    /* Dynamic allocation of matrix array */
12    adj_matrix = (int **) malloc (sizeof(int **)*nodes);
14      printf ("Fatal error in memory allocation!");
15      return -1;
16    }
17    for (r = 0; r < nodes; r++) {
18      adj_matrix[r] = (int *) malloc(sizeof(int)*nodes);
20        printf ("Fatal error in memory allocation!");
21        return -1;
22      }
23    }
24    for (r = 0; r < nodes; r++) {
25      for (c = 0; c < nodes; c++) {
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 (r > 0 && r <= nodes && c > 0 && c <= nodes){
38              adj_matrix[r - 1][c - 1] = 1;
39        if(d == 'U' || d == 'u'){
40        adj_matrix[c - 1][r - 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(r > 0 && c > 0);
47
49    printf("   ");
50    for (c = 0; c < nodes; c++) {
51      printf("%.1d ", c + 1);
52    }
53    printf("\n");
54    for (c = 0; c < nodes; c++) {
55      printf("---");
56    }
57    printf("\n");
58    for (r = 0; r < nodes; r++) {
59      printf("%.1d| ", r+1);
60      for (c = 0; c < nodes; 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

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

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.

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

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.

0

Similar topics related to this section