G-45. Prim's Algorithm - Minimum Spanning Tree - C++ and Java

In case you are thinking to buy courses, please check below:

---------------------------------------------------------------------------------------------------------------------------

[takeUforward]

Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too, you don't 😞

Do follow me on Instagram: striver_79

[ayushpatel]

All the newbies just wait for some time. When you will feel like banging your head due to dynamic programming problems, this channel will save you. He doesn't need any controversy to grow his channel. He is making videos to make quality content available on youtube for free.
His audience may be small but it is loyal. And when it comes to studying you only get this many view. Bcoz that is the real number of serious students.

[ary_]

Notes for self!
Required data structures
1. Min heap
2. Visited array
3. Mst list that will store all the edges that are a part of MST

Datatypes of our data structures
Visited array => int
Mst list => (weight, node name, node parent)



Steps
1. Mark the visited array as 0 for all the nodes

2. Start with 0th node and push
(0, 0, -1)
explanation: -1 means 0 is the genesis node
Mark 0 as visited

3. Push all the neighbours of 0 in pq *Do not mark them visited* (footnote 1)
Since its a min heap the edge with minimum weight will be at the top

4. Pick up the top edge, insert it in the mst, mark the picked node as visited, insert all neighbours of picked node into pq

5. keep repeating steps 3 and 4 untill all the nodes have been picked up and thats when the algorithm ends


footnote:
1. why to not mark it visited?
in bfs, when we push the element inside a queue we mark it as visited cause that element will be picked up later for sure (algorithm ends only when the queue is empty )
but in msts case even if we push the edge into pq, theres no surety that the edge will be picked up . when prims algo ends there are still a few non accepted edges present in the pq hence we only mark it visited once its picked up from pq

[nishantbhardwaj]

I didnt even know about how to calculate sum in an array around 6-7 months ago but now i had solved over 400 questions, Thank you so much for making this possible .

[pratiknagdeve]

I know lots of ignorant will come to hate you but after they know you very well they will come back to you to learn from you regarding competitive coding and DSA.

[bibaswanmukherjee]

Those who are coming here to criticize striver you don't know the struggle he did to get to the place where he is now and also his quality of teaching is top notch. His DP series is pure gold

[WhyYouNB]

Striver bhaiya ignore these freshers
Bache hai samaj utna hai nhi
U just keep moving forward
Love you

[harshal_bh]

as a working professional, I find ur videos are the best and in-line with important and freq asked dsa questions, completed dp playlist already, do not pay heed to these guys and carry on

[peterfromengland]

Whoever criticizing striver you will know the quality of this man, when you really start coding from heart

[JustForFun-zzhb]

At 8:45, node 2 is already visited so it should not be added to the priority queue. However it does not make any difference as node 2 is already visited and will not make any changes to our answer.

[shashankjoshi]

Really good Explanation - Just one feedback, start with Intuition first then move forward with the algorithm instead of other way around.

[aniruddhadas]

When you are starting your journey in DSA then you would grab those dhattarwal videos but as time elapses you will understand the worth of this man STRIVER❤️

[truthquest]

Striver is real teacher. And motivation for me
3million ka channel ek tweet ka reply karne ke liye video bana pada😂😂

[AashiSaxena-gz]

Best thing about him is that he emphasises on what we should not do. That's the way we remember it oo

[visase]

Thanks once Again Striver, For Freshers, this is great . But I feel that Prim's video in your old Graph playlist was more intuitional and crystal clear.

[sahilgupta]

you are amazing striver, wish to meet you someday !!

[Subhamoygpt]

Again a master piece. Thanks for this video striver. I think the last (2, 2, 3) should not be added as 2 is already visited when we are standing at 3.

[avocode]

waiting for new videos bhaiyya, and I really want to thank you, bcoz of your awesome and crystal clear lectures, I completed graphs like topic in just a week, all credit goes to you, thank u so much bhaiyya. 👍

[preranapatro]

U r the best ...no other content can ever be better then this one ..🥰🥰🥰🥰🥰🥰💌

[meetkgp]

I really enjoy watching your videos! I have two pieces of constructive feedback that I hope will be helpful:

1. [Addressed] Already pointed out by Just For Fun: At 8:37, node 2 is already visited, so it should not be added to the priority queue
2. At 16:20, during your explanation of the intuition, you covered Kruskal's MST instead of Prim's MST