Advertisement
saske_7

graph_representing.cpp

Sep 24th, 2017
109
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.99 KB | None | 0 0
  1. // A C Program to demonstrate adjacency list representation of graphs
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5.  
  6. struct AdjListNode
  7. {
  8.     int dest;
  9.     struct AdjListNode* next;
  10. };
  11.  
  12. struct AdjList
  13. {
  14.     struct AdjListNode *head;  // pointer to head node of list
  15. };
  16.  
  17. struct Graph
  18. {
  19.     int V;
  20.     struct AdjList* array;
  21. };
  22.  
  23. struct AdjListNode* newAdjListNode(int dest)
  24. {
  25.     struct AdjListNode* newNode =
  26.             (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
  27.     newNode->dest = dest;
  28.     newNode->next = NULL;
  29.     return newNode;
  30. }
  31.  
  32. struct Graph* createGraph(int V)
  33. {
  34.     struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
  35.     graph->V = V;
  36.  
  37.     graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));
  38.  
  39.     int i;
  40.     for (i = 0; i < V; ++i)
  41.         graph->array[i].head = NULL;
  42.  
  43.     return graph;
  44. }
  45.  
  46. void addEdge(struct Graph* graph, int src, int dest)
  47. {
  48.     struct AdjListNode* newNode = newAdjListNode(dest);
  49.     newNode->next = graph->array[src].head;
  50.     graph->array[src].head = newNode;
  51.  
  52.     newNode = newAdjListNode(src);
  53.     newNode->next = graph->array[dest].head;
  54.     graph->array[dest].head = newNode;
  55. }
  56.  
  57. void printGraph(struct Graph* graph)
  58. {
  59.     int v;
  60.     for (v = 0; v < graph->V; ++v)
  61.     {
  62.         struct AdjListNode* pCrawl = graph->array[v].head;
  63.         printf("\n Adjacency list of vertex %d\n head ", v);
  64.         while (pCrawl)
  65.         {
  66.             printf("-> %d", pCrawl->dest);
  67.             pCrawl = pCrawl->next;
  68.         }
  69.         printf("\n");
  70.     }
  71. }
  72.  
  73. int main()
  74. {
  75.     // create the graph given in above fugure
  76.     int V = 5;
  77.     struct Graph* graph = createGraph(V);
  78.     addEdge(graph, 0, 1);
  79.     addEdge(graph, 0, 4);
  80.     addEdge(graph, 1, 2);
  81.     addEdge(graph, 1, 3);
  82.     addEdge(graph, 1, 4);
  83.     addEdge(graph, 2, 3);
  84.     addEdge(graph, 3, 4);
  85.  
  86.     // print the adjacency list representation of the above graph
  87.     printGraph(graph);
  88.  
  89.     return 0;
  90. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement