Graph Representation using Adjacency List in C

This C program generates graph using Adjacency List Method.

Adjacency List – In this representation, the n rows of the adjacency matrix are represented as n linked lists. There is one list for each vertex in G. The nodes in list i represent the vertices that are adjacent from vertex i. Each node has at least two fields : vertex and next.

Here is the source code of the C program to create a graph using adjacency list. 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 <stdlib.h>
  3. #define new_node (struct node*)malloc(sizeof(struct node))
  4. struct node
  5. {
  6.     int vertex;
  7.     struct node *next;
  8. };
  9.  
  10. void main()
  11. {
  12.     int option;
  13.     do
  14.     {
  15.         printf("\n A Program to represent a Graph by using an Adjacency List \n ");
  16.         printf("\n 1. Directed Graph ");
  17.         printf("\n 2. Un-Directed Graph ");
  18.         printf("\n 3. Exit ");
  19.         printf("\n\n Select a proper option : ");
  20.         scanf("%d", &option);
  21.         switch(option)
  22.         {
  23.             case 1 : dir_graph();
  24.                      break;
  25.             case 2 : undir_graph();
  26.                      break;
  27.             case 3 : exit(0);
  28.         }
  29.     }while(1);
  30. }
  31. int dir_graph()
  32. {
  33.     struct node *adj_list[10], *p;
  34.     int n;
  35.     int in_deg, out_deg, i, j;
  36.     printf("\n How Many Vertices ? : ");
  37.     scanf("%d", &n);
  38.     for( i = 1 ; i <= n ; i++ )
  39.         adj_list[i] = NULL;
  40.     read_graph (adj_list, n);
  41.     printf("\n Vertex \t In_Degree \t Out_Degree \t Total_Degree ");
  42.     for (i = 1; i <= n ; i++ )
  43.     {
  44.         in_deg = out_deg = 0;
  45.         p = adj_list[i];
  46.         while( p != NULL )
  47.         {
  48.             out_deg++;
  49.             p = p -> next;
  50.         }
  51.         for ( j = 1 ; j <= n ; j++ )
  52.         {
  53.             p = adj_list[j];
  54.             while( p != NULL ) 
  55.             {
  56.                 if ( p -> vertex == i )
  57.                    in_deg++;
  58.                 p = p -> next;
  59.                 }
  60.              }
  61.              printf("\n\n %5d\t\t\t%d\t\t%d\t\t%d\n\n", i, in_deg, out_deg, in_deg + out_deg);
  62.         } 
  63.     return;
  64. }
  65. int undir_graph()
  66. {
  67.     struct node *adj_list[10], *p;
  68.     int deg, i, j, n;
  69.     printf("\n How Many Vertices ? : ");
  70.     scanf("%d", &n);
  71.     for ( i = 1 ; i <= n ; i++ )
  72.         adj_list[i] = NULL;
  73.     read_graph(adj_list, n);
  74.     printf("\n Vertex \t Degree ");
  75.     for ( i = 1 ; i <= n ; i++ )
  76.     {
  77.         deg = 0;
  78.         p = adj_list[i];
  79.         while( p != NULL )
  80. 	{
  81.             deg++;
  82.             p = p -> next;
  83.         }
  84.         printf("\n\n %5d \t\t %d\n\n", i, deg);
  85.     }
  86.     return;
  87. } 
  88. int read_graph ( struct node *adj_list[10], int n )
  89. {
  90.     int i, j;
  91.     char reply;
  92.     struct node *p, *c;
  93.     for ( i = 1 ; i <= n ; i++ )
  94.     {
  95.         for ( j = 1 ; j <= n ; j++ )
  96.         {
  97.             if ( i == j )
  98.                 continue;
  99.             printf("\n Vertices %d & %d are Adjacent ? (Y/N) :", i, j);
  100.             scanf("%c", &reply);
  101.             if ( reply == 'y' || reply == 'Y' )
  102.             {
  103.                 c = new_node;
  104.                 c -> vertex = j;
  105.                 c -> next = NULL;
  106.                 if ( adj_list[i] == NULL )
  107.                     adj_list[i] = c;
  108.                 else
  109.                 {
  110.                     p = adj_list[i];
  111.                     while ( p -> next != NULL )
  112.                         p = p -> next;
  113.                     p -> next = c;
  114. 		} 
  115.             }
  116.         } 
  117.     }
  118.     return;
  119. }

$ gcc graph.c -o graph
$ ./graph
 A Program to represent a Graph by using an Adjacency Matrix method 
 
 1. Directed Graph 
 2. Un-Directed Graph 
 3. Exit 
 
 Select a proper option : 
 How Many Vertices ? : 
 Vertices 1 & 2 are Adjacent ? (Y/N) : N
 Vertices 1 & 3 are Adjacent ? (Y/N) : Y
 Vertices 1 & 4 are Adjacent ? (Y/N) : Y
 Vertices 2 & 1 are Adjacent ? (Y/N) : Y
 Vertices 2 & 3 are Adjacent ? (Y/N) : Y
 Vertices 2 & 4 are Adjacent ? (Y/N) : N
 Vertices 3 & 1 are Adjacent ? (Y/N) : Y
 Vertices 3 & 2 are Adjacent ? (Y/N) : Y
 Vertices 3 & 4 are Adjacent ? (Y/N) : Y
 Vertices 4 & 1 are Adjacent ? (Y/N) : Y
 Vertices 4 & 2 are Adjacent ? (Y/N) : N
 Vertices 4 & 3 are Adjacent ? (Y/N) : Y
 Vertex 	 In_Degree 	 Out_Degree 	 Total_Degree 
 
     1			2		0		2
 
 
 
     2			1		2		3
 
 
 
     3			0		1		1
 
 
 
     4			1		1		2
 
 
 A Program to represent a Graph by using an Adjacency Matrix method 
 
 1. Directed Graph 
 2. Un-Directed Graph 
 3. Exit

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.