Graph Representation using Incidence Matrix in C

This C program represents graph using incidence matrix.

An incidence matrix is a matrix where each column represents an edge connected to two vertices.

Here is the source code of the C program to represent graph using incidence matrix. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C Program to Describe the Representation of Graph using Incidence Matrix
  3.  */
  4. #include<stdio.h>
  5. struct node
  6. {
  7.     int from, to;
  8. }a[5], t;
  9. void addEdge(int am[][5], int i, int j, int in)
  10. {
  11.     int p, q;
  12.     a[in].from = i;
  13.     a[in].to = j;
  14.     for ( p = 0; p <= in; p++)
  15.     {
  16.         for (q = p + 1; q <= in; q++)
  17.         {
  18.             if (a[p].from > a[q].from)
  19.             {
  20.                 t = a[p];
  21.                 a[p] = a[q];
  22.                 a[q] = t;
  23.             }
  24.             else if (a[p].from == a[q].from)
  25.             {
  26.                 if (a[p].to > a[q].to)
  27.                 {
  28.                     t = a[p];
  29.                     a[p] = a[q];
  30.                     a[q] = t;
  31.                 }
  32.             }
  33.             else
  34.             {
  35.                 continue;
  36.             }
  37.         }
  38.     }
  39. }
  40. int main()
  41. {
  42.     int n, c = 0, x, y, ch, i, j;
  43.     int am[5][5];
  44.     printf("Enter the no of vertices\n");
  45.     scanf("%d", &n);
  46.  
  47.     for (i = 0; i < 5; i++)
  48.     {
  49.         for (j = 0; j < 5; j++)
  50.         {
  51.             am[i][j] = 0;
  52.         }
  53.     }
  54.     while (ch != -1)
  55.     {
  56.         printf("Enter the nodes between which you want to introduce edge\n");
  57.         scanf("%d%d", &x, &y);
  58.         addEdge(am, x, y, c);
  59.         c++;
  60.         printf("Press -1 to exit\n");
  61.         scanf("%d", &ch);
  62.     }    
  63.     for (j = 0; j < c; j++)
  64.     {
  65.         am[a[j].from][j] = 1;
  66.         am[a[j].to][j] = 1;
  67.     }
  68.     for (i = 0; i < n; i++)
  69.     {
  70.         for (j = 0; j < c; j++)
  71.         {
  72.             printf("%d\t" ,am[i][j]);
  73.         }
  74.         printf("\n");
  75.     } 
  76. }

$ gcc incidence_matrix.c -o incidence_matrix
$ ./incidence_matrix
Enter the no of vertices
5
Enter the nodes between which you want to introduce edge
0
1
Press -1 to exit
0
Enter the nodes between which you want to introduce edge
0
2
Press -1 to exit
0
Enter the nodes between which you want to introduce edge
2
3
Press -1 to exit
0
Enter the nodes between which you want to introduce edge
1
4
Press -1 to exit
0
Enter the nodes between which you want to introduce edge
0
3
Press -1 to exit
-1
1       1       1       0       0
1       0       0       1       0
0       1       0       0       1
0       0       1       0       1
0       0       0       1       0

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.