Write a program, which given inputs as integer pairs representing edges, creates an adjacency matrix for a graph.

Source Code

Brief explanation is provided after the source code.

#include <stdio.h>
#include <stdlib.h>

#define V 8

int main(void){
    int i, j, a, adj[V][V];
    for(i = 0; i < V; i++)
        for(j = 0; j < V; j++)
            adj[i][j] = 0; /* initialize matrix */
    for(i = 0; i < V; i++)
        adj[i][i] = 1;  /* major diagonal */

    /* Now read in edges as vertex pairs */
    printf("\nEnter vertex pairs - Press  to end\n");
    while(scanf("%d%d", &i, &j) == 2) {
        adj[i][j] = 1;
        adj[j][i] = 1;
    }
    /* display matrix */
    for(i = 0; i < V; i++)
        if(i == 0)
            printf("%6d", i);   /* 1st column label indented */
        else
            printf("%3d", i);   /* other column labels */
    printf("\n");

    for(i = 0; i < V; i++){
        printf("%3d", i);   /* row label*/
        for(j = 0; j < V; j++)
            printf("%3d", adj[i][j]);
        printf("\n");
    }
    return 0;
}

When you compile and execute the above program it produces the following result on Linux:

Enter vertex pairs - Press  to end
0 1 3 4 6 7 9 8 12 4 5 0 2 4 6 17
     0  1  2  3  4  5  6  7
  0  1  1  0  0  0  1  0  0
  1  1  1  0  0  0  0  0  0
  2  0  0  1  0  1  0  0  0
  3  0  0  0  1  1  0  0  0
  4  0  0  1  1  1  0  0  0
  5  1  0  0  0  1  1  0  0
  6  0  0  0  0  0  0  1  1
  7  0  0  0  0  0  0  1  1

Brief Explanation

  • An adjacency matrix is a 2-D matrix used to represent a graph. One can tell if there is an edge between vertex i and vertex j by checking the cell at the intersection of row i and column j: if it contains 1, there is an edge between the vertices; if it is zero, there is no edge between the vertices.
  • From the result of the program, the cell at the intersection of each of the vertex pairs provided contains 1 which means there is an edge between the vertices.
  • For an undirected graph, the matrix is symmetrical about the major diagonal because the entry at cell[i][j] is the same entry in cell [j][i]. By convention, the major diagonal cells are assigned the value 1 (each vertex is connected to itself).

Add comment


Security code
Refresh