{"id":26284,"date":"2017-10-26T20:51:46","date_gmt":"2017-10-26T15:21:46","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26284"},"modified":"2017-10-26T20:51:46","modified_gmt":"2017-10-26T15:21:46","slug":"greedy-algorithms-set-6-prims-mst-adjacency-list-representation","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/greedy-algorithms-set-6-prims-mst-adjacency-list-representation\/","title":{"rendered":"Greedy Algorithms | Set 6 (Prim\u2019s MST for Adjacency List Representation)"},"content":{"rendered":"<p>We recommend to read following two posts as a prerequisite of this post.<span id=\"more-27580\"><\/span><\/p>\n<p><strong>1.<\/strong> <a href=\"http:\/\/www.geeksforgeeks.org\/archives\/27455\">Greedy Algorithms | Set 5 (Prim\u2019s Minimum Spanning Tree (MST))<\/a><br \/>\n<strong>2.<\/strong> <a href=\"http:\/\/www.geeksforgeeks.org\/archives\/27134\">Graph and its representations<\/a><\/p>\n<p>We have discussed <a href=\"http:\/\/www.geeksforgeeks.org\/archives\/27455\">Prim\u2019s algorithm and its implementation for adjacency matrix representation of graphs<\/a>. The time complexity for the matrix representation is O(V^2). In this post, O(ELogV) algorithm for adjacency list representation is discussed.<br \/>\nAs discussed in the previous post, in Prim\u2019s algorithm, two sets are maintained, one set contains list of vertices already included in MST, other set contains vertices not yet included. With adjacency list representation, all vertices of a graph can be traversed in O(V+E) time using <a href=\"http:\/\/www.geeksforgeeks.org\/archives\/18382\">BFS<\/a>. The idea is to traverse all vertices of graph using <a href=\"http:\/\/www.geeksforgeeks.org\/archives\/18382\">BFS <\/a>and use a Min Heap to store the vertices not yet included in MST. Min Heap is used as a priority queue to get the minimum weight edge from the <a href=\"http:\/\/en.wikipedia.org\/wiki\/Cut_%28graph_theory%29\">cut<\/a>. Min Heap is used as time complexity of operations like extracting minimum element and decreasing key value is O(LogV) in Min Heap.<\/p>\n[ad type=\u201dbanner\u201d]\n<p>Following are the detailed steps.<br \/>\n<strong>1) <\/strong>Create a Min Heap of size V where V is the number of vertices in the given graph. Every node of min heap contains vertex number and key value of the vertex.<br \/>\n<strong>2)<\/strong> Initialize Min Heap with first vertex as root (the key value assigned to first vertex is 0). The key value assigned to all other vertices is INF (infinite).<br \/>\n<strong>3) <\/strong>While Min Heap is not empty, do following<br \/>\n\u2026..<strong>a)<\/strong> Extract the min value node from Min Heap. Let the extracted vertex be u.<br \/>\n\u2026..<strong>b)<\/strong> For every adjacent vertex v of u, check if v is in Min Heap (not yet included in MST). If v is in Min Heap and its key value is more than weight of u-v, then update the key value of v as weight of u-v.<\/p>\n<p>Let us understand the above algorithm with the following example:<\/p>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter size-full wp-image-26253\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/Fig-11-1.png\" alt=\"Prim\u2019s MST for Adjacency List Representation)\" width=\"714\" height=\"333\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/Fig-11-1.png 714w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/Fig-11-1-300x140.png 300w\" sizes=\"(max-width: 714px) 100vw, 714px\" \/><\/p>\n<p>Initially, key value of first vertex is 0 and INF (infinite) for all other vertices. So vertex 0 is extracted from Min Heap and key values of vertices adjacent to 0 (1 and 7) are updated. Min Heap contains all vertices except vertex 0.<br \/>\nThe vertices in green color are the vertices included in MST.<\/p>\n<p><img decoding=\"async\" class=\"aligncenter size-full wp-image-26254\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/MST1-1.png\" alt=\"Initially, key value of first vertex is 0 and INF (infinite) for all other vertices. So vertex 0 is extracted from Min Heap and key values of vertices adjacent to 0 (1 and 7) are updated. Min Heap contains all vertices except vertex 0. The vertices in green color are the vertices included in MST.\" width=\"80\" height=\"139\" \/><\/p>\n<p>Since key value of vertex 1 is minimum among all nodes in Min Heap, it is extracted from Min Heap and key values of vertices adjacent to 1 are updated (Key is updated if the a vertex is not in Min Heap and previous key value is greater than the weight of edge from 1 to the adjacent). Min Heap contains all vertices except vertex 0 and 1.<\/p>\n<p><img decoding=\"async\" class=\"aligncenter size-full wp-image-26255\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/MST2-1.png\" alt=\"Since key value of vertex 1 is minimum among all nodes in Min Heap, it is extracted from Min Heap and key values of vertices adjacent to 1 are updated (Key is updated if the a vertex is not in Min Heap and previous key value is greater than the weight of edge from 1 to the adjacent). Min Heap contains all vertices except vertex 0 and 1.\" width=\"150\" height=\"139\" \/><\/p>\n<p>Since key value of vertex 7 is minimum among all nodes in Min Heap, it is extracted from Min Heap and key values of vertices adjacent to 7 are updated (Key is updated if the a vertex is not in Min Heap and previous key value is greater than the weight of edge from 7 to the adjacent). Min Heap contains all vertices except vertex 0, 1 and 7.<img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-26256\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/MST3-1.png\" alt=\"(Prim\u2019s MST for Adjacency List Representation)\" width=\"150\" height=\"139\" \/><\/p>\n<p>Since key value of vertex 6 is minimum among all nodes in Min Heap, it is extracted from Min Heap and key values of vertices adjacent to 6 are updated (Key is updated if the a vertex is not in Min Heap and previous key value is greater than the weight of edge from 6 to the adjacent). Min Heap contains all vertices except vertex 0, 1, 7 and 6.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-26257\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/MST4-1.png\" alt=\"Prim\u2019s MST for Adjacency List Representation)\" width=\"210\" height=\"139\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/MST4-1.png 210w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/MST4-1-130x86.png 130w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/MST4-1-187x124.png 187w\" sizes=\"(max-width: 210px) 100vw, 210px\" \/><\/p>\n<p>The above steps are repeated for rest of the nodes in Min Heap till Min Heap becomes empty<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-26298\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/MST5-2.png\" alt=\"Prim\u2019s MST for Adjacency List Representation)\" width=\"260\" height=\"139\" \/><\/p>\n<p><strong>C Programming<\/strong><\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%23include%20%3Cstdio.h%3E%0A%23include%20%3Cstdlib.h%3E%0A%23include%20%3Climits.h%3E%0A%20%0A%2F%2F%20A%20structure%20to%20represent%20a%20node%20in%20adjacency%20list%0Astruct%20AdjListNode%0A%7B%0A%20%20%20%20int%20dest%3B%0A%20%20%20%20int%20weight%3B%0A%20%20%20%20struct%20AdjListNode*%20next%3B%0A%7D%3B%0A%20%0A%2F%2F%20A%20structure%20to%20represent%20an%20adjacency%20liat%0Astruct%20AdjList%0A%7B%0A%20%20%20%20struct%20AdjListNode%20*head%3B%20%20%2F%2F%20pointer%20to%20head%20node%20of%20list%0A%7D%3B%0A%20%0A%2F%2F%20A%20structure%20to%20represent%20a%20graph.%20A%20graph%20is%20an%20array%20of%20adjacency%20lists.%0A%2F%2F%20Size%20of%20array%20will%20be%20V%20(number%20of%20vertices%20in%20graph)%0Astruct%20Graph%0A%7B%0A%20%20%20%20int%20V%3B%0A%20%20%20%20struct%20AdjList*%20array%3B%0A%7D%3B%0A%20%0A%2F%2F%20A%20utility%20function%20to%20create%20a%20new%20adjacency%20list%20node%0Astruct%20AdjListNode*%20newAdjListNode(int%20dest%2C%20int%20weight)%0A%7B%0A%20%20%20%20struct%20AdjListNode*%20newNode%20%3D%0A%20%20%20%20%20%20%20%20%20%20%20%20(struct%20AdjListNode*)%20malloc(sizeof(struct%20AdjListNode))%3B%0A%20%20%20%20newNode-%3Edest%20%3D%20dest%3B%0A%20%20%20%20newNode-%3Eweight%20%3D%20weight%3B%0A%20%20%20%20newNode-%3Enext%20%3D%20NULL%3B%0A%20%20%20%20return%20newNode%3B%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20that%20creates%20a%20graph%20of%20V%20vertices%0Astruct%20Graph*%20createGraph(int%20V)%0A%7B%0A%20%20%20%20struct%20Graph*%20graph%20%3D%20(struct%20Graph*)%20malloc(sizeof(struct%20Graph))%3B%0A%20%20%20%20graph-%3EV%20%3D%20V%3B%0A%20%0A%20%20%20%20%2F%2F%20Create%20an%20array%20of%20adjacency%20lists.%20%20Size%20of%20array%20will%20be%20V%0A%20%20%20%20graph-%3Earray%20%3D%20(struct%20AdjList*)%20malloc(V%20*%20sizeof(struct%20AdjList))%3B%0A%20%0A%20%20%20%20%20%2F%2F%20Initialize%20each%20adjacency%20list%20as%20empty%20by%20making%20head%20as%20NULL%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20V%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20graph-%3Earray%5Bi%5D.head%20%3D%20NULL%3B%0A%20%0A%20%20%20%20return%20graph%3B%0A%7D%0A%20%0A%2F%2F%20Adds%20an%20edge%20to%20an%20undirected%20graph%0Avoid%20addEdge(struct%20Graph*%20graph%2C%20int%20src%2C%20int%20dest%2C%20int%20weight)%0A%7B%0A%20%20%20%20%2F%2F%20Add%20an%20edge%20from%20src%20to%20dest.%20%20A%20new%20node%20is%20added%20to%20the%20adjacency%0A%20%20%20%20%2F%2F%20list%20of%20src.%20%20The%20node%20is%20added%20at%20the%20begining%0A%20%20%20%20struct%20AdjListNode*%20newNode%20%3D%20newAdjListNode(dest%2C%20weight)%3B%0A%20%20%20%20newNode-%3Enext%20%3D%20graph-%3Earray%5Bsrc%5D.head%3B%0A%20%20%20%20graph-%3Earray%5Bsrc%5D.head%20%3D%20newNode%3B%0A%20%0A%20%20%20%20%2F%2F%20Since%20graph%20is%20undirected%2C%20add%20an%20edge%20from%20dest%20to%20src%20also%0A%20%20%20%20newNode%20%3D%20newAdjListNode(src%2C%20weight)%3B%0A%20%20%20%20newNode-%3Enext%20%3D%20graph-%3Earray%5Bdest%5D.head%3B%0A%20%20%20%20graph-%3Earray%5Bdest%5D.head%20%3D%20newNode%3B%0A%7D%0A%20%0A%2F%2F%20Structure%20to%20represent%20a%20min%20heap%20node%0Astruct%20MinHeapNode%0A%7B%0A%20%20%20%20int%20%20v%3B%0A%20%20%20%20int%20key%3B%0A%7D%3B%0A%20%0A%2F%2F%20Structure%20to%20represent%20a%20min%20heap%0Astruct%20MinHeap%0A%7B%0A%20%20%20%20int%20size%3B%20%20%20%20%20%20%2F%2F%20Number%20of%20heap%20nodes%20present%20currently%0A%20%20%20%20int%20capacity%3B%20%20%2F%2F%20Capacity%20of%20min%20heap%0A%20%20%20%20int%20*pos%3B%20%20%20%20%20%2F%2F%20This%20is%20needed%20for%20decreaseKey()%0A%20%20%20%20struct%20MinHeapNode%20**array%3B%0A%7D%3B%0A%20%0A%2F%2F%20A%20utility%20function%20to%20create%20a%20new%20Min%20Heap%20Node%0Astruct%20MinHeapNode*%20newMinHeapNode(int%20v%2C%20int%20key)%0A%7B%0A%20%20%20%20struct%20MinHeapNode*%20minHeapNode%20%3D%0A%20%20%20%20%20%20%20%20%20%20%20(struct%20MinHeapNode*)%20malloc(sizeof(struct%20MinHeapNode))%3B%0A%20%20%20%20minHeapNode-%3Ev%20%3D%20v%3B%0A%20%20%20%20minHeapNode-%3Ekey%20%3D%20key%3B%0A%20%20%20%20return%20minHeapNode%3B%0A%7D%0A%20%0A%2F%2F%20A%20utilit%20function%20to%20create%20a%20Min%20Heap%0Astruct%20MinHeap*%20createMinHeap(int%20capacity)%0A%7B%0A%20%20%20%20struct%20MinHeap*%20minHeap%20%3D%0A%20%20%20%20%20%20%20%20%20(struct%20MinHeap*)%20malloc(sizeof(struct%20MinHeap))%3B%0A%20%20%20%20minHeap-%3Epos%20%3D%20(int%20*)malloc(capacity%20*%20sizeof(int))%3B%0A%20%20%20%20minHeap-%3Esize%20%3D%200%3B%0A%20%20%20%20minHeap-%3Ecapacity%20%3D%20capacity%3B%0A%20%20%20%20minHeap-%3Earray%20%3D%0A%20%20%20%20%20%20%20%20%20(struct%20MinHeapNode**)%20malloc(capacity%20*%20sizeof(struct%20MinHeapNode*))%3B%0A%20%20%20%20return%20minHeap%3B%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20to%20swap%20two%20nodes%20of%20min%20heap.%20Needed%20for%20min%20heapify%0Avoid%20swapMinHeapNode(struct%20MinHeapNode**%20a%2C%20struct%20MinHeapNode**%20b)%0A%7B%0A%20%20%20%20struct%20MinHeapNode*%20t%20%3D%20*a%3B%0A%20%20%20%20*a%20%3D%20*b%3B%0A%20%20%20%20*b%20%3D%20t%3B%0A%7D%0A%20%0A%2F%2F%20A%20standard%20function%20to%20heapify%20at%20given%20idx%0A%2F%2F%20This%20function%20also%20updates%20position%20of%20nodes%20when%20they%20are%20swapped.%0A%2F%2F%20Position%20is%20needed%20for%20decreaseKey()%0Avoid%20minHeapify(struct%20MinHeap*%20minHeap%2C%20int%20idx)%0A%7B%0A%20%20%20%20int%20smallest%2C%20left%2C%20right%3B%0A%20%20%20%20smallest%20%3D%20idx%3B%0A%20%20%20%20left%20%3D%202%20*%20idx%20%2B%201%3B%0A%20%20%20%20right%20%3D%202%20*%20idx%20%2B%202%3B%0A%20%0A%20%20%20%20if%20(left%20%3C%20minHeap-%3Esize%20%26%26%0A%20%20%20%20%20%20%20%20minHeap-%3Earray%5Bleft%5D-%3Ekey%20%3C%20minHeap-%3Earray%5Bsmallest%5D-%3Ekey%20)%0A%20%20%20%20%20%20smallest%20%3D%20left%3B%0A%20%0A%20%20%20%20if%20(right%20%3C%20minHeap-%3Esize%20%26%26%0A%20%20%20%20%20%20%20%20minHeap-%3Earray%5Bright%5D-%3Ekey%20%3C%20minHeap-%3Earray%5Bsmallest%5D-%3Ekey%20)%0A%20%20%20%20%20%20smallest%20%3D%20right%3B%0A%20%0A%20%20%20%20if%20(smallest%20!%3D%20idx)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20The%20nodes%20to%20be%20swapped%20in%20min%20heap%0A%20%20%20%20%20%20%20%20MinHeapNode%20*smallestNode%20%3D%20minHeap-%3Earray%5Bsmallest%5D%3B%0A%20%20%20%20%20%20%20%20MinHeapNode%20*idxNode%20%3D%20minHeap-%3Earray%5Bidx%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Swap%20positions%0A%20%20%20%20%20%20%20%20minHeap-%3Epos%5BsmallestNode-%3Ev%5D%20%3D%20idx%3B%0A%20%20%20%20%20%20%20%20minHeap-%3Epos%5BidxNode-%3Ev%5D%20%3D%20smallest%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Swap%20nodes%0A%20%20%20%20%20%20%20%20swapMinHeapNode(%26minHeap-%3Earray%5Bsmallest%5D%2C%20%26minHeap-%3Earray%5Bidx%5D)%3B%0A%20%0A%20%20%20%20%20%20%20%20minHeapify(minHeap%2C%20smallest)%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20to%20check%20if%20the%20given%20minHeap%20is%20ampty%20or%20not%0Aint%20isEmpty(struct%20MinHeap*%20minHeap)%0A%7B%0A%20%20%20%20return%20minHeap-%3Esize%20%3D%3D%200%3B%0A%7D%0A%20%0A%2F%2F%20Standard%20function%20to%20extract%20minimum%20node%20from%20heap%0Astruct%20MinHeapNode*%20extractMin(struct%20MinHeap*%20minHeap)%0A%7B%0A%20%20%20%20if%20(isEmpty(minHeap))%0A%20%20%20%20%20%20%20%20return%20NULL%3B%0A%20%0A%20%20%20%20%2F%2F%20Store%20the%20root%20node%0A%20%20%20%20struct%20MinHeapNode*%20root%20%3D%20minHeap-%3Earray%5B0%5D%3B%0A%20%0A%20%20%20%20%2F%2F%20Replace%20root%20node%20with%20last%20node%0A%20%20%20%20struct%20MinHeapNode*%20lastNode%20%3D%20minHeap-%3Earray%5BminHeap-%3Esize%20-%201%5D%3B%0A%20%20%20%20minHeap-%3Earray%5B0%5D%20%3D%20lastNode%3B%0A%20%0A%20%20%20%20%2F%2F%20Update%20position%20of%20last%20node%0A%20%20%20%20minHeap-%3Epos%5Broot-%3Ev%5D%20%3D%20minHeap-%3Esize-1%3B%0A%20%20%20%20minHeap-%3Epos%5BlastNode-%3Ev%5D%20%3D%200%3B%0A%20%0A%20%20%20%20%2F%2F%20Reduce%20heap%20size%20and%20heapify%20root%0A%20%20%20%20\u2013minHeap-%3Esize%3B%0A%20%20%20%20minHeapify(minHeap%2C%200)%3B%0A%20%0A%20%20%20%20return%20root%3B%0A%7D%0A%20%0A%2F%2F%20Function%20to%20decreasy%20key%20value%20of%20a%20given%20vertex%20v.%20This%20function%0A%2F%2F%20uses%20pos%5B%5D%20of%20min%20heap%20to%20get%20the%20current%20index%20of%20node%20in%20min%20heap%0Avoid%20decreaseKey(struct%20MinHeap*%20minHeap%2C%20int%20v%2C%20int%20key)%0A%7B%0A%20%20%20%20%2F%2F%20Get%20the%20index%20of%20v%20in%20%20heap%20array%0A%20%20%20%20int%20i%20%3D%20minHeap-%3Epos%5Bv%5D%3B%0A%20%0A%20%20%20%20%2F%2F%20Get%20the%20node%20and%20update%20its%20key%20value%0A%20%20%20%20minHeap-%3Earray%5Bi%5D-%3Ekey%20%3D%20key%3B%0A%20%0A%20%20%20%20%2F%2F%20Travel%20up%20while%20the%20complete%20tree%20is%20not%20hepified.%0A%20%20%20%20%2F%2F%20This%20is%20a%20O(Logn)%20loop%0A%20%20%20%20while%20(i%20%26%26%20minHeap-%3Earray%5Bi%5D-%3Ekey%20%3C%20minHeap-%3Earray%5B(i%20-%201)%20%2F%202%5D-%3Ekey)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Swap%20this%20node%20with%20its%20parent%0A%20%20%20%20%20%20%20%20minHeap-%3Epos%5BminHeap-%3Earray%5Bi%5D-%3Ev%5D%20%3D%20(i-1)%2F2%3B%0A%20%20%20%20%20%20%20%20minHeap-%3Epos%5BminHeap-%3Earray%5B(i-1)%2F2%5D-%3Ev%5D%20%3D%20i%3B%0A%20%20%20%20%20%20%20%20swapMinHeapNode(%26minHeap-%3Earray%5Bi%5D%2C%20%20%26minHeap-%3Earray%5B(i%20-%201)%20%2F%202%5D)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20move%20to%20parent%20index%0A%20%20%20%20%20%20%20%20i%20%3D%20(i%20-%201)%20%2F%202%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20to%20check%20if%20a%20given%20vertex%0A%2F%2F%20\u2019v\u2019%20is%20in%20min%20heap%20or%20not%0Abool%20isInMinHeap(struct%20MinHeap%20*minHeap%2C%20int%20v)%0A%7B%0A%20%20%20if%20(minHeap-%3Epos%5Bv%5D%20%3C%20minHeap-%3Esize)%0A%20%20%20%20%20return%20true%3B%0A%20%20%20return%20false%3B%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20used%20to%20print%20the%20constructed%20MST%0Avoid%20printArr(int%20arr%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20%20for%20(int%20i%20%3D%201%3B%20i%20%3C%20n%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20printf(%22%25d%20-%20%25d%5Cn%22%2C%20arr%5Bi%5D%2C%20i)%3B%0A%7D%0A%20%0A%2F%2F%20The%20main%20function%20that%20constructs%20Minimum%20Spanning%20Tree%20(MST)%0A%2F%2F%20using%20Prim\u2019s%20algorithm%0Avoid%20PrimMST(struct%20Graph*%20graph)%0A%7B%0A%20%20%20%20int%20V%20%3D%20graph-%3EV%3B%2F%2F%20Get%20the%20number%20of%20vertices%20in%20graph%0A%20%20%20%20int%20parent%5BV%5D%3B%20%20%20%2F%2F%20Array%20to%20store%20constructed%20MST%0A%20%20%20%20int%20key%5BV%5D%3B%20%20%20%20%20%20%2F%2F%20Key%20values%20used%20to%20pick%20minimum%20weight%20edge%20in%20cut%0A%20%0A%20%20%20%20%2F%2F%20minHeap%20represents%20set%20E%0A%20%20%20%20struct%20MinHeap*%20minHeap%20%3D%20createMinHeap(V)%3B%0A%20%0A%20%20%20%20%2F%2F%20Initialize%20min%20heap%20with%20all%20vertices.%20Key%20value%20of%0A%20%20%20%20%2F%2F%20all%20vertices%20(except%200th%20vertex)%20is%20initially%20infinite%0A%20%20%20%20for%20(int%20v%20%3D%201%3B%20v%20%3C%20V%3B%20%2B%2Bv)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20parent%5Bv%5D%20%3D%20-1%3B%0A%20%20%20%20%20%20%20%20key%5Bv%5D%20%3D%20INT_MAX%3B%0A%20%20%20%20%20%20%20%20minHeap-%3Earray%5Bv%5D%20%3D%20newMinHeapNode(v%2C%20key%5Bv%5D)%3B%0A%20%20%20%20%20%20%20%20minHeap-%3Epos%5Bv%5D%20%3D%20v%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Make%20key%20value%20of%200th%20vertex%20as%200%20so%20that%20it%0A%20%20%20%20%2F%2F%20is%20extracted%20first%0A%20%20%20%20key%5B0%5D%20%3D%200%3B%0A%20%20%20%20minHeap-%3Earray%5B0%5D%20%3D%20newMinHeapNode(0%2C%20key%5B0%5D)%3B%0A%20%20%20%20minHeap-%3Epos%5B0%5D%20%20%20%3D%200%3B%0A%20%0A%20%20%20%20%2F%2F%20Initially%20size%20of%20min%20heap%20is%20equal%20to%20V%0A%20%20%20%20minHeap-%3Esize%20%3D%20V%3B%0A%20%0A%20%20%20%20%2F%2F%20In%20the%20followin%20loop%2C%20min%20heap%20contains%20all%20nodes%0A%20%20%20%20%2F%2F%20not%20yet%20added%20to%20MST.%0A%20%20%20%20while%20(!isEmpty(minHeap))%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Extract%20the%20vertex%20with%20minimum%20key%20value%0A%20%20%20%20%20%20%20%20struct%20MinHeapNode*%20minHeapNode%20%3D%20extractMin(minHeap)%3B%0A%20%20%20%20%20%20%20%20int%20u%20%3D%20minHeapNode-%3Ev%3B%20%2F%2F%20Store%20the%20extracted%20vertex%20number%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Traverse%20through%20all%20adjacent%20vertices%20of%20u%20(the%20extracted%0A%20%20%20%20%20%20%20%20%2F%2F%20vertex)%20and%20update%20their%20key%20values%0A%20%20%20%20%20%20%20%20struct%20AdjListNode*%20pCrawl%20%3D%20graph-%3Earray%5Bu%5D.head%3B%0A%20%20%20%20%20%20%20%20while%20(pCrawl%20!%3D%20NULL)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20int%20v%20%3D%20pCrawl-%3Edest%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20v%20is%20not%20yet%20included%20in%20MST%20and%20weight%20of%20u-v%20is%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20less%20than%20key%20value%20of%20v%2C%20then%20update%20key%20value%20and%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20parent%20of%20v%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(isInMinHeap(minHeap%2C%20v)%20%26%26%20pCrawl-%3Eweight%20%3C%20key%5Bv%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20key%5Bv%5D%20%3D%20pCrawl-%3Eweight%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20parent%5Bv%5D%20%3D%20u%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20decreaseKey(minHeap%2C%20v%2C%20key%5Bv%5D)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20pCrawl%20%3D%20pCrawl-%3Enext%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20print%20edges%20of%20MST%0A%20%20%20%20printArr(parent%2C%20V)%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20%2F%2F%20Let%20us%20create%20the%20graph%20given%20in%20above%20fugure%0A%20%20%20%20int%20V%20%3D%209%3B%0A%20%20%20%20struct%20Graph*%20graph%20%3D%20createGraph(V)%3B%0A%20%20%20%20addEdge(graph%2C%200%2C%201%2C%204)%3B%0A%20%20%20%20addEdge(graph%2C%200%2C%207%2C%208)%3B%0A%20%20%20%20addEdge(graph%2C%201%2C%202%2C%208)%3B%0A%20%20%20%20addEdge(graph%2C%201%2C%207%2C%2011)%3B%0A%20%20%20%20addEdge(graph%2C%202%2C%203%2C%207)%3B%0A%20%20%20%20addEdge(graph%2C%202%2C%208%2C%202)%3B%0A%20%20%20%20addEdge(graph%2C%202%2C%205%2C%204)%3B%0A%20%20%20%20addEdge(graph%2C%203%2C%204%2C%209)%3B%0A%20%20%20%20addEdge(graph%2C%203%2C%205%2C%2014)%3B%0A%20%20%20%20addEdge(graph%2C%204%2C%205%2C%2010)%3B%0A%20%20%20%20addEdge(graph%2C%205%2C%206%2C%202)%3B%0A%20%20%20%20addEdge(graph%2C%206%2C%207%2C%201)%3B%0A%20%20%20%20addEdge(graph%2C%206%2C%208%2C%206)%3B%0A%20%20%20%20addEdge(graph%2C%207%2C%208%2C%207)%3B%0A%20%0A%20%20%20%20PrimMST(graph)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D%0A\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>\u00a0<\/p>\n<p>Output:<\/p>\n<pre>0 - 1\r\n5 - 2\r\n2 - 3\r\n3 - 4\r\n6 - 5\r\n7 - 6\r\n0 - 7\r\n2 - 8<\/pre>\n<p><strong>Time Complexity:<\/strong> The time complexity of the above code\/algorithm looks O(V^2) as there are two nested while loops. If we take a closer look, we can observe that the statements in inner loop are executed O(V+E) times (similar to BFS). The inner loop has decreaseKey() operation which takes O(LogV) time. So overall time complexity is O(E+V)*O(LogV) which is O((E+V)*LogV) = O(ELogV) (For a connected graph, V = O(E))<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>Greedy Algorithms | Set 6 (Prim\u2019s MST for Adjacency List Representation) &#8211; Minimum Spanning Tree &#8211; We have discussed Prim\u2019s algorithm and its implement.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70144,76379],"tags":[78204,78199,78200,70785,78202,78201,78205,78203],"class_list":["post-26284","post","type-post","status-publish","format-standard","hentry","category-greedy-algorithm","category-minimum-spanning-tree","tag-kruskal-algorithm-geeksforgeeks","tag-prims-algorithm-c-priority-queue","tag-prims-algorithm-implementation-java","tag-prims-algorithm-in-c","tag-prims-algorithm-priority-queue","tag-prims-algorithm-using-adjacency-list","tag-prims-algorithm-using-adjacency-matrix","tag-prims-algorithm-using-heap"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26284","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26284"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26284\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26284"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26284"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26284"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}