![\"\"](\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/Prim\u2019s-algorithm-using-priority_queue-in-STL.png\")
<\/p>\nGiven an undirected, connected and weighted graph, find Minimum Spanning Tree (MST) of the graph using Prim\u2019s algorithm.<\/p>\n
<\/p>\n
Input : Adjacency List representation\r\n of above graph\r\nOutput : Edges in MST\r\n 0 - 1\r\n 1 - 2\r\n 2 - 3\r\n 3 - 4\r\n 2 - 5\r\n 5 - 6\r\n 6 - 7\r\n 2 - 8\r\n\r\n\r\nNote : <\/strong> There are two possible MSTs, the other\r\n MST includes edge 0-7 in place of 1-2.<\/pre>\nWe have discussed below Prim\u2019s MST implementations.<\/p>\n
\n
- Prim\u2019s Algorithm for Adjacency Matrix Representation (In C\/C++ with time complexity O(v2<\/sup>)<\/li>\n
- Prim\u2019s Algorithm for Adjacency List Representation (In C with Time Complexity O(ELogV))<\/li>\n<\/ul>\n
The second implementation is time complexity wise better, but is really complex as we have implemented our own priority queue. STL provides priority_queue, but the provided priority queue doesn\u2019t support decrease key operation. And in Prim\u2019s algorithm, we need a priority queue and below operations on priority queue :<\/p>\n
\n
- ExtractMin : from all those vertices which have not yet been included in MST, we need to get vertex with minimum key value.<\/li>\n
- DecreaseKey : After extracting vertex we need to update keys of its adjacent vertices, and if new key is smaller, then update that in data structure.<\/li>\n<\/ul>\n
The algorithm discussed here can be modified so that decrease key is never required. The idea is, not to insert all vertices in priority queue, but only those which are not MST and have been visited through a vertex that has included in MST. We keep track of vertices included in MST in a separate boolean array inMST[].<\/p>\n
1) Initialize keys of all vertices as infinite and \r\n parent of every vertex as -1.\r\n\r\n2) Create an empty priority_queue pq. Every item\r\n of pq is a pair (weight, vertex). Weight (or \r\n key) is used used as first item of pair\r\n as first item is by default used to compare\r\n two pairs.\r\n\r\n3) Initialize all vertices as not part of MST yet.\r\n We use boolean array inMST[] for this purpose.\r\n This array is required to make sure that an already\r\n considered vertex is not included in pq again. This\r\n is where Ptim's implementation differs from Dijkstra.\r\n In Dijkstr's algorithm, we didn't need this array as\r\n distances always increase. We require this array here \r\n because key value of a processed vertex may decrease\r\n if not checked.\r\n\r\n4) Insert source vertex into pq and make its key as 0.\r\n\r\n5) While either pq doesn't become empty \r\n a) Extract minimum key vertex from pq. \r\n Let the extracted vertex be u.\r\n\r\n b) Include u in MST using inMST[u] = true.\r\n\r\n c) Loop through all adjacent of u and do \r\n following for every vertex v.\r\n\r\n \/\/ If weight of edge (u,v) is smaller than\r\n \/\/ key of v and v is not already in MST\r\n If inMST[v] = false && key[v] > weight(u, v)\r\n\r\n (i) Update key of v, i.e., do\r\n key[v] = weight(u, v)\r\n (ii) Insert v into the pq \r\n (iv) parent[v] = u\r\n \r\n6) Print MST edges using parent array.<\/pre>\nBelow is C++ implementation of above idea.<\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20STL%20implementation%20of%20Prim\u2019s%20algorithm%20for%20MST%0A%23include%3Cbits%2Fstdc%2B%2B.h%3E%0Ausing%20namespace%20std%3B%0A%23%20define%20INF%200x3f3f3f3f%0A%20%0A%2F%2F%20iPair%20%3D%3D%3E%20%20Integer%20Pair%0Atypedef%20pair%3Cint%2C%20int%3E%20iPair%3B%0A%20%0A%2F%2F%20This%20class%20represents%20a%20directed%20graph%20using%0A%2F%2F%20adjacency%20list%20representation%0Aclass%20Graph%0A%7B%0A%20%20%20%20int%20V%3B%20%20%20%20%2F%2F%20No.%20of%20vertices%0A%20%0A%20%20%20%20%2F%2F%20In%20a%20weighted%20graph%2C%20we%20need%20to%20store%20vertex%0A%20%20%20%20%2F%2F%20and%20weight%20pair%20for%20every%20edge%0A%20%20%20%20list%3C%20pair%3Cint%2C%20int%3E%20%3E%20*adj%3B%0A%20%0Apublic%3A%0A%20%20%20%20Graph(int%20V)%3B%20%20%2F%2F%20Constructor%0A%20%0A%20%20%20%20%2F%2F%20function%20to%20add%20an%20edge%20to%20graph%0A%20%20%20%20void%20addEdge(int%20u%2C%20int%20v%2C%20int%20w)%3B%0A%20%0A%20%20%20%20%2F%2F%20Print%20MST%20using%20Prim\u2019s%20algorithm%0A%20%20%20%20void%20primMST()%3B%0A%7D%3B%0A%20%0A%2F%2F%20Allocates%20memory%20for%20adjacency%20list%0AGraph%3A%3AGraph(int%20V)%0A%7B%0A%20%20%20%20this-%3EV%20%3D%20V%3B%0A%20%20%20%20adj%20%3D%20new%20list%3CiPair%3E%20%5BV%5D%3B%0A%7D%0A%20%0Avoid%20Graph%3A%3AaddEdge(int%20u%2C%20int%20v%2C%20int%20w)%0A%7B%0A%20%20%20%20adj%5Bu%5D.push_back(make_pair(v%2C%20w))%3B%0A%20%20%20%20adj%5Bv%5D.push_back(make_pair(u%2C%20w))%3B%0A%7D%0A%20%0A%2F%2F%20Prints%20shortest%20paths%20from%20src%20to%20all%20other%20vertices%0Avoid%20Graph%3A%3AprimMST()%0A%7B%0A%20%20%20%20%2F%2F%20Create%20a%20priority%20queue%20to%20store%20vertices%20that%0A%20%20%20%20%2F%2F%20are%20being%20preinMST.%20This%20is%20weird%20syntax%20in%20C%2B%2B.%0A%20%20%20%20%2F%2F%20Refer%20below%20link%20for%20details%20of%20this%20syntax%0A%20%20%20%20%2F%2F%20http%3A%2F%2Fgeeksquiz.com%2Fimplement-min-heap-using-stl%2F%0A%20%20%20%20priority_queue%3C%20iPair%2C%20vector%20%3CiPair%3E%20%2C%20greater%3CiPair%3E%20%3E%20pq%3B%0A%20%0A%20%20%20%20int%20src%20%3D%200%3B%20%2F%2F%20Taking%20vertex%200%20as%20source%0A%20%0A%20%20%20%20%2F%2F%20Create%20a%20vector%20for%20keys%20and%20initialize%20all%0A%20%20%20%20%2F%2F%20keys%20as%20infinite%20(INF)%0A%20%20%20%20vector%3Cint%3E%20key(V%2C%20INF)%3B%0A%20%0A%20%20%20%20%2F%2F%20To%20store%20parent%20array%20which%20in%20turn%20store%20MST%0A%20%20%20%20vector%3Cint%3E%20parent(V%2C%20-1)%3B%0A%20%0A%20%20%20%20%2F%2F%20To%20keep%20track%20of%20vertices%20included%20in%20MST%0A%20%20%20%20vector%3Cbool%3E%20inMST(V%2C%20false)%3B%0A%20%0A%20%20%20%20%2F%2F%20Insert%20source%20itself%20in%20priority%20queue%20and%20initialize%0A%20%20%20%20%2F%2F%20its%20key%20as%200.%0A%20%20%20%20pq.push(make_pair(0%2C%20src))%3B%0A%20%20%20%20key%5Bsrc%5D%20%3D%200%3B%0A%20%0A%20%20%20%20%2F*%20Looping%20till%20priority%20queue%20becomes%20empty%20*%2F%0A%20%20%20%20while%20(!pq.empty())%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20The%20first%20vertex%20in%20pair%20is%20the%20minimum%20key%0A%20%20%20%20%20%20%20%20%2F%2F%20vertex%2C%20extract%20it%20from%20priority%20queue.%0A%20%20%20%20%20%20%20%20%2F%2F%20vertex%20label%20is%20stored%20in%20second%20of%20pair%20(it%0A%20%20%20%20%20%20%20%20%2F%2F%20has%20to%20be%20done%20this%20way%20to%20keep%20the%20vertices%0A%20%20%20%20%20%20%20%20%2F%2F%20sorted%20key%20(key%20must%20be%20first%20item%0A%20%20%20%20%20%20%20%20%2F%2F%20in%20pair)%0A%20%20%20%20%20%20%20%20int%20u%20%3D%20pq.top().second%3B%0A%20%20%20%20%20%20%20%20pq.pop()%3B%0A%20%0A%20%20%20%20%20%20%20%20inMST%5Bu%5D%20%3D%20true%3B%20%20%2F%2F%20Include%20vertex%20in%20MST%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20\u2019i\u2019%20is%20used%20to%20get%20all%20adjacent%20vertices%20of%20a%20vertex%0A%20%20%20%20%20%20%20%20list%3C%20pair%3Cint%2C%20int%3E%20%3E%3A%3Aiterator%20i%3B%0A%20%20%20%20%20%20%20%20for%20(i%20%3D%20adj%5Bu%5D.begin()%3B%20i%20!%3D%20adj%5Bu%5D.end()%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Get%20vertex%20label%20and%20weight%20of%20current%20adjacent%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20of%20u.%0A%20%20%20%20%20%20%20%20%20%20%20%20int%20v%20%3D%20(*i).first%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20int%20weight%20%3D%20(*i).second%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20%20If%20v%20is%20not%20in%20MST%20and%20weight%20of%20(u%2Cv)%20is%20smaller%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20than%20current%20key%20of%20v%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(inMST%5Bv%5D%20%3D%3D%20false%20%26%26%20key%5Bv%5D%20%3E%20weight)%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%20%2F%2F%20Updating%20key%20of%20v%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20key%5Bv%5D%20%3D%20weight%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20pq.push(make_pair(key%5Bv%5D%2C%20v))%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%7D%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%20using%20parent%20array%0A%20%20%20%20for%20(int%20i%20%3D%201%3B%20i%20%3C%20V%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20printf(%22%25d%20-%20%25d%5Cn%22%2C%20parent%5Bi%5D%2C%20i)%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20methods%20of%20graph%20class%0Aint%20main()%0A%7B%0A%20%20%20%20%2F%2F%20create%20the%20graph%20given%20in%20above%20fugure%0A%20%20%20%20int%20V%20%3D%209%3B%0A%20%20%20%20Graph%20g(V)%3B%0A%20%0A%20%20%20%20%2F%2F%20%20making%20above%20shown%20graph%0A%20%20%20%20g.addEdge(0%2C%201%2C%204)%3B%0A%20%20%20%20g.addEdge(0%2C%207%2C%208)%3B%0A%20%20%20%20g.addEdge(1%2C%202%2C%208)%3B%0A%20%20%20%20g.addEdge(1%2C%207%2C%2011)%3B%0A%20%20%20%20g.addEdge(2%2C%203%2C%207)%3B%0A%20%20%20%20g.addEdge(2%2C%208%2C%202)%3B%0A%20%20%20%20g.addEdge(2%2C%205%2C%204)%3B%0A%20%20%20%20g.addEdge(3%2C%204%2C%209)%3B%0A%20%20%20%20g.addEdge(3%2C%205%2C%2014)%3B%0A%20%20%20%20g.addEdge(4%2C%205%2C%2010)%3B%0A%20%20%20%20g.addEdge(5%2C%206%2C%202)%3B%0A%20%20%20%20g.addEdge(6%2C%207%2C%201)%3B%0A%20%20%20%20g.addEdge(6%2C%208%2C%206)%3B%0A%20%20%20%20g.addEdge(7%2C%208%2C%207)%3B%0A%20%0A%20%20%20%20g.primMST()%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
Output :<\/p>\n
0 - 1\r\n1 - 2\r\n2 - 3\r\n3 - 4\r\n2 - 5\r\n5 - 6\r\n6 - 7\r\n2 - 8<\/pre>\nTime complexity : O(E Log V))<\/p>\n","protected":false},"excerpt":{"rendered":"
Prim\u2019s algorithm using priority_queue in STL – STL Implementation of Algorithms – Given an undirected, connected and weighted graph, find Minimum Spanning<\/p>\n","protected":false},"author":1,"featured_media":31289,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[81350,81360],"tags":[81897,71248,70766,70792,81896,81900,81903,81905,81898,81901,70763,81908,70770,70775,78200,70785,76602,81907,70804,70787,78202,70778,81902,78201,78203,81895,70776,71258,81904,70800,70801,70777,81899,81906],"class_list":["post-27567","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-graph","category-stl-implementation-of-algorithms","tag-algorithme-de-prim","tag-difference-between-prims-and-kruskal-algorithm","tag-prim","tag-prim-algorithm","tag-prim-algorithm-c","tag-prim-algorithm-example","tag-prim-algorithm-java","tag-prim-algorithm-pseudocode","tag-prim-algorithmus","tag-prim-algoritmasi","tag-prims-algorithm","tag-prims-algorithm-animation","tag-prims-algorithm-example","tag-prims-algorithm-for-minimum-spanning-tree","tag-prims-algorithm-implementation-java","tag-prims-algorithm-in-c","tag-prims-algorithm-java","tag-prims-algorithm-java-code","tag-prims-algorithm-minimum-spanning-tree","tag-prims-algorithm-ppt","tag-prims-algorithm-priority-queue","tag-prims-algorithm-pseudocode","tag-prims-algorithm-python","tag-prims-algorithm-using-adjacency-list","tag-prims-algorithm-using-heap","tag-prims-algorithm-using-priority-queue-in-c","tag-prims-algorithm-with-example","tag-primary-s","tag-primes-algorithm","tag-prims-algo","tag-prims-and-kruskal-algorithm","tag-prims-and-kruskal-algorithm-with-example","tag-what-is-prim","tag-what-is-prims-algorithm"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27567","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=27567"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27567\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/31289"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27567"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27567"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27567"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}