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

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!