C Program to Implement Adjacency List

This is a C Program to implement Adjacency List. An array of linked lists is used. Size of the array is equal to number of vertices. Let the array be array[]. An entry array[i] represents the linked list of vertices adjacent to the ith vertex. This representation can also be used to represent a weighted graph. The weights of edges can be stored in nodes of linked lists. Following is adjacency list representation of the above graph.

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

  1. // A C Program to demonstrate adjacency list representation of graphs
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5.  
  6. // A structure to represent an adjacency list node
  7. struct AdjListNode {
  8.     int dest;
  9.     struct AdjListNode* next;
  10. };
  11.  
  12. // A structure to represent an adjacency liat
  13. struct AdjList {
  14.     struct AdjListNode *head; // pointer to head node of list
  15. };
  16.  
  17. // A structure to represent a graph. A graph is an array of adjacency lists.
  18. // Size of array will be V (number of vertices in graph)
  19. struct Graph {
  20.     int V;
  21.     struct AdjList* array;
  22. };
  23.  
  24. // A utility function to create a new adjacency list node
  25. struct AdjListNode* newAdjListNode(int dest) {
  26.     struct AdjListNode* newNode = (struct AdjListNode*) malloc(
  27.             sizeof(struct AdjListNode));
  28.     newNode->dest = dest;
  29.     newNode->next = NULL;
  30.     return newNode;
  31. }
  32.  
  33. // A utility function that creates a graph of V vertices
  34. struct Graph* createGraph(int V) {
  35.     struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
  36.     graph->V = V;
  37.  
  38.     // Create an array of adjacency lists.  Size of array will be V
  39.     graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));
  40.  
  41.     // Initialize each adjacency list as empty by making head as NULL
  42.     int i;
  43.     for (i = 0; i < V; ++i)
  44.         graph->array[i].head = NULL;
  45.  
  46.     return graph;
  47. }
  48.  
  49. // Adds an edge to an undirected graph
  50. void addEdge(struct Graph* graph, int src, int dest) {
  51.     // Add an edge from src to dest.  A new node is added to the adjacency
  52.     // list of src.  The node is added at the begining
  53.     struct AdjListNode* newNode = newAdjListNode(dest);
  54.     newNode->next = graph->array[src].head;
  55.     graph->array[src].head = newNode;
  56.  
  57.     // Since graph is undirected, add an edge from dest to src also
  58.     newNode = newAdjListNode(src);
  59.     newNode->next = graph->array[dest].head;
  60.     graph->array[dest].head = newNode;
  61. }
  62.  
  63. // A utility function to print the adjacenncy list representation of graph
  64. void printGraph(struct Graph* graph) {
  65.     int v;
  66.     for (v = 0; v < graph->V; ++v) {
  67.         struct AdjListNode* pCrawl = graph->array[v].head;
  68.         printf("\n Adjacency list of vertex %d\n head ", v);
  69.         while (pCrawl) {
  70.             printf("-> %d", pCrawl->dest);
  71.             pCrawl = pCrawl->next;
  72.         }
  73.         printf("\n");
  74.     }
  75. }
  76.  
  77. // Driver program to test above functions
  78. int main() {
  79.     // create the graph given in above fugure
  80.     int V = 5;
  81.     struct Graph* graph = createGraph(V);
  82.     addEdge(graph, 0, 1);
  83.     addEdge(graph, 0, 4);
  84.     addEdge(graph, 1, 2);
  85.     addEdge(graph, 1, 3);
  86.     addEdge(graph, 1, 4);
  87.     addEdge(graph, 2, 3);
  88.     addEdge(graph, 3, 4);
  89.  
  90.     // print the adjacency list representation of the above graph
  91.     printGraph(graph);
  92.  
  93.     return 0;
  94. }

Output:

$ gcc AdjacencyList.c
$ ./a.out
 
Adjacency list of vertex 0
 head -> 4-> 1
 
 Adjacency list of vertex 1
 head -> 4-> 3-> 2-> 0
 
 Adjacency list of vertex 2
 head -> 3-> 1
 
 Adjacency list of vertex 3
 head -> 4-> 2-> 1
 
 Adjacency list of vertex 4
 head -> 3-> 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.

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.