C Program to Implement Adjacency Matrix

This is a C Program to implement Adjacency Matrix. Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph. Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j. Adjacency matrix for undirected graph is always symmetric. Adjacency Matrix is also used to represent weighted graphs. If adj[i][j] = w, then there is an edge from vertex i to vertex j with weight w.

Here is source code of the C Program to Implement Adjacency Matrix. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include<stdio.h>
  2. #include<conio.h>
  3. #define max 20
  4. int adj[max][max];
  5. int n;
  6. main() {
  7.     int choice;
  8.     int node, origin, destin;
  9.     create_graph();
  10.     while (1) {
  11.         printf("1.Insert a node\n");
  12.         printf("2.Delete a node\n");
  13.         printf("3.Dispaly\n");
  14.         printf("4.Exit\n");
  15.         printf("Enter your choice : ");
  16.         scanf("%d", &choice);
  17.         switch (choice) {
  18.         case 1:
  19.             insert_node();
  20.             break;
  21.         case 2:
  22.             printf("Enter a node to be deleted : ");
  23.             fflush(stdin);
  24.             scanf("%d", &node);
  25.             delete_node(node);
  26.             break;
  27.         case 3:
  28.             display();
  29.             break;
  30.         case 4:
  31.             exit(0);
  32.         default:
  33.             printf("Wrong choice\n");
  34.             break;
  35.         }
  36.     }
  37.     getch();
  38. }
  39.  
  40. create_graph() {
  41.     int i, max_edges, origin, destin;
  42.  
  43.     printf("Enter number of nodes : ");
  44.     scanf("%d", &n);
  45.     max_edges = n * (n - 1);
  46.  
  47.     for (i = 1; i <= max_edges; i++) {
  48.         printf("Enter edge %d( 0 0 ) to quit : ", i);
  49.         scanf("%d %d", &origin, &destin);
  50.         if ((origin == 0) && (destin == 0))
  51.             break;
  52.         if (origin > n || destin > n || origin <= 0 || destin <= 0) {
  53.             printf("Invalid edge!\n");
  54.             i--;
  55.         } else
  56.             adj[origin][destin] = 1;
  57.     }
  58. }
  59.  
  60. display() {
  61.     int i, j;
  62.     for (i = 1; i <= n; i++) {
  63.         for (j = 1; j <= n; j++)
  64.             printf("%4d", adj[i][j]);
  65.         printf("\n");
  66.     }
  67. }
  68.  
  69. insert_node() {
  70.     int i;
  71.     n++;
  72.     printf("The inserted node is %d \n", n);
  73.     for (i = 1; i <= n; i++) {
  74.         adj[i][n] = 0;
  75.         adj[n][i] = 0;
  76.     }
  77. }
  78.  
  79. void delete_node(char u) {
  80.     int i, j;
  81.     if (n == 0) {
  82.         printf("Graph is empty\n");
  83.         return;
  84.     }
  85.     if (u > n) {
  86.         printf("This node is not present in the graph\n");
  87.         return;
  88.     }
  89.     for (i = u; i <= n - 1; i++)
  90.         for (j = 1; j <= n; j++) {
  91.             adj[j][i] = adj[j][i + 1];
  92.             adj[i][j] = adj[i + 1][j];
  93.         }
  94.     n--;
  95. }

Output:

$ gcc AdjacencyMatrix.c
$ ./a.out
 
6
0 1
1 2
1 4
3 4
4 5 
5 3
5 2
0 0
3
4
Enter number of nodes : 6
Enter edge 1( 0 0 ) to quit : 1 2
Enter edge 2( 0 0 ) to quit : 1 4
Enter edge 3( 0 0 ) to quit : 3 4
Enter edge 4( 0 0 ) to quit : 4 5
Enter edge 5( 0 0 ) to quit : 5 3
Enter edge 6( 0 0 ) to quit : 5 2
Enter edge 7( 0 0 ) to quit : 0 0
1.Insert a node
2.Delete a node
3.Dispaly
4.Exit
Enter your choice :   3
   0   1   0   1   0   0
   0   0   0   0   0   0
   0   0   0   1   0   0
   0   0   0   0   1   0
   0   1   1   0   0   0
   0   0   0   0   0   0
1.Insert a node
2.Delete a node
3.Dispaly
4.Exit
Enter your choice : 4

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement
advertisement

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.