Hello people..! This is a special extension to my post on Prim’s Algorithm. Here, I give you a different implementation of Prim’s Algorithm which uses C++ STL. So, those who are uncomfortable with using pointers should feel just at home with this…! Provided you know C++ STL..! 😉 … Some of the features of this code are –
- The Adjacency List used is exactly as in Adjacency List using C++ STL
- The Min Heap is unchanged from the former post on Prim’s Algorithm. We stick to the array of structs.
- The Prim’s algorithm function uses C++ reference parameters to yield the necessary results.
Keep comparing every strange line with the simple C code… I’m sure you’ll get it..! 🙂 … Feel free to comment if you have any doubts..! Keep practicing..! Happy Coding..! 😀
8 thoughts on “Prim’s Algorithm using C++ STL”
Can you please tell how to make prims algorithm with the use of bfs and priority queue in c++.
Hi, Deepak…! I don’t think you can make Prim’s Algorithm with BFS.. Because BFS is meant for unweighted graphs… If you do find a way to do it please share it here in the comments 🙂
Can you please implement using priority que stl in c++.
Sure!.. The post will be updated in a few days 🙂
The above code segfaults on a simple tree, searching from 1, tree: 1-2 1-3 1-4 1-5 1-6; gcc 6.4.0. This graph is connected, is it not?
The bad access occurs in ExtractMin() when we try to return min uninitialized.
Sorry for the first (somewhat curt) reply. I found your Github repo with updated code, and it has no errors, so far. I’m interested in modifying it so I don’t have to use integer weights, and will get back to you if I have problems.
Sadly, your code (which you updated using STL objects like list and which I found at your GitHub repo) emits compilation errors from a modern compiler. Modern C++ (evidently) prohibits variable length arrays of non-POD types (“plain old data”). The hangup is going to be passing indexable (by vertex) arrays of adjacency lists to the algorithm. Also, your Prim algorithm seems to be full of twists and turns. Of course, not to you, who (I trust) wrote it.