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

GfG-Problem Link: bit.ly/3ABwwRP
C++/Java/Codes and Notes Link: takeuforward.org/data-structu...
DP Series: • Striver's Dynamic Prog...
SDE Sheet: takeuforward.org/interviews/s...
Check out our Website for curated resources:
Our Second Channel: / @striver_79
In case you are thinking to buy courses, please check below:
Code "takeuforward" for 15% off at GFG: practice.geeksforgeeks.org/co...
Code "takeuforward" for 20% off on sys-design: get.interviewready.io?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/invite/xexnpc4u
Take 750 rs free Amazon Stock from me: indmoney.onelink.me/RmHC/idje...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v3cO/8hu879t0
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
---------------------------------------------------------------------------------------------------------------------------

[@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

[@ujjawal_]

thanks for your valuable content 🙂

[@rishav144]

understood ♨️

[@youtubegaming7791]

bhaiya notes link

[@dr.stereo_4046]

Oh ho maje aa gye tree me to 😁. Thanks bhaiya

[@dr.stereo_4046]

Understood understood understood 😊

[@ary_21]

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

[@RANGER_Rajat]

👍

[@ayushanand5659]

Copy mein bana leta bhai

[@IshaanJoshi-ms9mb]

@@ayushanand5659 lol

[@valendradangi1822]

I think 0 is not marked visited while pushing into the queue but when it is taken out of queue

[@JustForFun-zz2hb]

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.

[@takeUforward]

OOps sorry, yes

[@jadejaharshvardhansinh8332]

Yeah I watched it Second time and then noticed it😅 good point!

[@Saurabh-fe2bg]

Paused the vdo...and searched for the comment which mentioned this

[@praneethkonduru9000]

nice one i also observed this

[@gigglezone3432]

Yea I was searching for this comment, why nobody pointed out the error. Got it!!

[@kshitijmishra2716]

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❤

[@argonystarc3298]

Dhattarwal's videos are as useless as your linkedin posts.

[@tusharverma4202]

Exactly!

[@yashsingh3040]

that microsoft girl has also tought graph theory but that isnt worth it.she didnt discuss no ques. striver is best

[@lakshsinghania]

i have been following u on linkedin awesome content! i appreciate it

[@kshitijmishra2716]

@@lakshsinghania thanks buddy

[@ayushpatel2171]

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.

[@shivanshnamdev6417]

😹 lol having 3 lakh subs And Views 5-10 k I think paid Views Hain 😹😹😹

[@ayushpatel2171]

@@shivanshnamdev6417 Advanced topic itne hi log padhte hai. Waki log bas c aur java ka one shot hi deakh te rehte hai.

[@shivanshnamdev6417]

😹 Baas Karo yaar Itna Kon defend karta Hai chalo maan Liya Aap sahi per itne hi agrr advance padhte toh 10-15 k subs baas hone the baaki kya churake laaye

[@atheisttttt]

@@ayushpatel2171 💀

[@atheisttttt]

@@shivanshnamdev6417 4 saal baad ana

[@bibaswanmukherjee6853]

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

[@pritammehta7770]

But what he said was right ?

[@vaibhavnayak233]

@@pritammehta7770yeah. Maybe using a girl thumb line was wrong point but rest of the part is 100% right.

[@JohnWick-oj6bw]

@@vaibhavnayak233 He was 100% right about that too. See, how she played victim card when faced with criticism. And all the toxic ppl coming to defend her??? Only cuz she's a female

[@anshumaan1024]

@@JohnWick-oj6bw kon critcise kr rha tha bhai ?🙄

[@Moch117]

Who is criticizing him and for what ? @@pritammehta7770

[@WhyYouN00B]

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

[@peterfromengland8663]

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

[@Moch117]

Who is criticizing him and for what ?

[@truthquest4404]

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

[@MN-gn7lt]

Ye daar hona jaruri hai❤😂💯

[@user-fz1yv4lq4d]

@@MN-gn7lt tere behen ko koi Bolega na tab mat bolna

[@Rajat_maurya]

ye dar hame accha laga

[@nishantbhardwaj9757]

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 .

[@pratiknagdeve3259]

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.

[@harshalbhoir1262]

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

[@visase2036]

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.

[@takeUforward]

But it was a bit complex, this is more straightforward and easy 😅

[@pulkitagrawal8046]

I too felt in the same way

[@shigoeditz7079]

Thankyou Striver for such a beautiful explanation ❤ and a Happy New Year ❤🎉

[@avocode1487]

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. 👍

[@sukhpreetsingh5200]

Understood and awesome as usual

[@neilbohr6015]

in the worst case scenario wouldn't TC be V(logV+V-1+logV) for each vertex we are travelling all its edges(which can be at max v-1 in complete graph for a vertex ) 🤔🤔 just thinking

[@itz_me_imraan02]

Perfect as always ♥

[@dhruvsolanki4473]

Amazing explanation, thank you for teaching us.

[@raghavagrawal9240]

Waiting for the next videos of this series!

[@preranapatro2414]

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

[@rishav144]

thanks Striver for great playlist

[@funnyanimation888]

It cleared almost all of the dought and got a very good intution .

[@user-ml4ol5tl2s]

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.

[@nishantbhardwaj9757]

Your data structures and algorithms playlist is amazing sir tbh i had watched all your playlist and again tbh i had watched babbar bhaiyaa’s also , both of you are amazing no hate to anyone , just keep the good work going .

[@krishanpratap3286]

Maja aa gaya bhayiya love your content

[@varunakrishnani7688]

Understood! :) Thank you bhaiya! 🙏🏻😊

[@abhishekudiya8638]

Firstly Striver your content is awesome and this graph series is top-notch ..can you tell us this series is completed or if more videos will be come in the future in this graph series and when will be new videos coming .

[@PriyaGupta-sg4sm]

Why did we take (2,2,3) at 8:45, we see before added if the node is already visited no? pls clarify

[@stith_pragya]

Thank You So Much for this wonderful video............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@cinime]

Understood! Super awesome explanation as always, thank you very much!!

[@arpitrajput6424]

Code according to explanation C++ int spanningTree(int V, vector adj[]) { // code here vector vis(V,0); vector mst; priority_queue pq; pq.push({0,{0,-1}}); int sum=0; while(pq.size()){ int dis = pq.top().first; int node = pq.top().second.first; int parent = pq.top().second.second; pq.pop(); if(vis[node])continue; if(parent!= -1) mst.push_back({node,parent}); vis[node] = 1; sum += dis; for(auto it : adj[node]){ int adjNode = it[0]; int edgeW = it[1]; if(!vis[adjNode]){ pq.push({edgeW,{adjNode,node}}); } } } // printing mst // for(auto it : mst){ // cout

[@user-qn7lt2xb1n]

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

[@udaytewary3809]

Understood bhaiya 🙏❤️

[@adebisisheriff159]

Thanks striver!!!!

[@mihirsaini592]

Thank you striver

[@euvsielr]

I completely agree with you bhaiya.

[@mdyousufgazi4030]

what should i change to the code to get mst for example like this " {(0, 2), (1, 2), (2, 3), (3, 4)} "

[@harshprit_k]

Abhi Aman Aman kar rhe h sabhi, 3 saal ke baad yahi se placement k liye padhenge 😂

[@vegitokun]

Bhai m 11th class m hun, iss bande ka content shi m achcha h kya? Abhi jee ki prep kar raha hun.

[@harshprit_k]

@@vegitokun yes bro, content is damn good, having opinion about something shouldn't affect your decision. Or just wait for 3 years, you will automatically know why i am saying this..

[@Rajat_maurya]

ekdam sahi bat bole bhai...abhi fresher hai inko kya hi pata job lena kitta mushkil hai

[@shikharshiromani2728]

Is it possible to add all the edges at once in priority queue, then pop them one by one (check if already visited, check if already in MST) marking the nodes visited as we pop from the priority queue and push it to MST?

[@takeUforward]

noh, we will follow similar approach in kruskal, you will see how to deal with it

[@infinite9953]

Understood 🙌

[@shashankjoshi8250]

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

[@amanasrani6405]

Thank You Striver, If you are not there pata nhi kya hota thousand of student ka Amazingggggg! also hats off to your patience doing dry run❤❤❤❤❤❤❤

[@simmi641]

Striver=huge love+respect❤

[@saibunny1253]

striver bhai today i understood prim's algorithm using ds priority queue to find minimum spanning tree thank you

[@meetjoshi9829]

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

[@shreyanshagrawal3115]

what should be Prim's then?

[@lakshsinghania]

@@shreyanshagrawal3115 exactly!

[@shivamnegi7552]

no bro , both prim's kruskal are greedy , intuition for both are same we doing greedy in both cases .

[@bulioh]

Yeah I was confused at 16:24 since I don't think that edge (1,4,3) would be in the priority queue yet

[@gamerglobe4839]

is this approach also same like finding shortest distance from source to destination since we are adding distances into the sum variable?

[@original_gangsta_]

Understood 🔥🔥

[@h108pranavshinde3]

God bless you bro ! You are taking too much effort to teach. This shows your dedication and passion 🔥🔥✨✨

[@UECAshutoshKumar]

Thank you sir 😊

[@yasharthagarwal3937]

Hey Striver Why can't we use Dijkstra's Algo for finding mst? It also states the minimum cost to travel all the nodes . Prim's also states to find minimum cost while visiting all nodes. At any given point of time we can use both for single source or we can find minimum distance by changing the source node from both algo.

[@virusnetic]

but in Dijkstra's Algo, we are finding all the path with minimum cost from a particular source to a particular destination node In the example used if the source is used the Dijkstra's Algo will return -> [0, 2, 1, 3, 2] this is not necessarily the mst we are seeking for (we don't need the sum but the minimum edges only). as there will be a edge b/w 2 and 4 try dry run of the algo you will get it

[@rishabhinc2936]

in djikstra it can consider more than n-1 edges

[@parshchoradia9909]

Understood Sir!

[@hope-jh7bv]

understood💙

[@krishnavyaskondle5707]

can we use this algorithm to find the shortest distance between two nodes

[@anmolkaushik4576]

Understood!

[@Rajat_maurya]

Please make video on union find (DSU) questions... not able to solve leetcode ones

[@amitp277]

Awesome 👏👏 this one is similar to Dijkstra's

[@p38_amankuldeep75]

understood🔥🔥🔥

[@nishant1456]

CP is incomplete without this guy

[@AmanGupta-ib5ss]

understood :)

[@ACUCSPRADEEPB-up9ne]

Understood✌️

[@user-tk2vg5jt3l]

Thank you bhaiya

[@EngineersNeedJobs]

understood!

[@garimakumari4346]

thanks man

[@vaibhavmurarka5179]

can't we use set in the same way like we used djikstra's won't it be more efficient since we will also erase the itrns which we won't need

[@SadhanaSharma]

Thank you sirrrrrrr

[@VIVardhan5130]

You are still more than god for some people striver

[@sanky6114]

Understood !!!

[@gauravlokwani8623]

Thank you so much for this video, could please also make the video on kruskal algorithm for this new playlist..??

[@takeUforward]

Yes it will come soon.

[@_MS98]

Thanks 🐻‍❄🐻‍❄

[@poorviagrawal8926]

plz make a video on question - max cashflow among friends

[@dreamyme543]

Understood:)

[@gautamsaxena4647]

understood bhaiya

[@surjendupal7576]

Sir asking off topic question....... What's your tech stack? Means which technology you are proficient?

[@satyamroy3783]

Is their will be more videos in this series ?

[@mriduljain6809]

Understood Bhaiya

[@priyanshvatsal9791]

Understood 😇

[@23ritik]

Sir make start array and strings series also please for interview purpose

[@codebypg]

understood

[@prakharsinha4145]

Can anybody tell why are we doing something like this ( ( x , y ) - > x.distance - y.distance ) in priority queue declaration in Java ?

[@sanamdeepsingh7914]

Understood

[@dharmenderkumar2841]

UNDERSTOOD

[@user-ne5ti5gd1i]

Why would 2,3,2 be picked before 2,4,2? If there's a clash in min value, FIFO should be applied right since it's a queue after all?

[@CodeMode9313]

Habibi ek aur mast bideo banaye ho

[@salmankhader1258]

Why cant we mark the node as vis while pushing into the priority queue

[@aayushojha3088]

I think the adj nodes wala loop ,will run for 2E , ans no of adjnodes or neighbours in undirected graph is 2E

[@matmister1769]

vector adj[] Can anyone explain to me how this data structure is working? it is an array of vectors of vectors. Not sure why a 3 level dagta structure is needed.

[@amanbhadani8840]

This time prims algorithm is little easy and not complex than from previous graph series.

[@aniruddhadas1778]

@8:44 node 2 should not be included in the priority queue as node 2 was already visited

[@keepitup3077]

Driver bhaiya aapke to maje hai yaar😁😁😁

[@tushar7305]

Priority queue top element take O(logn) time ?

[@aryansindhav5695]

Is this series finished?

[@Now_I_am_all_fired_up]

Plz make vedion on : Bridges in a graph

[@HardikJain_YT]

actually better

[@LokeshSharma-hm5jz]

Understood, its getting TLE, i used set of unvisited nodes while helps me to break while loop but still getting TLE in coding ninja, Maybe kruskal will help me. Thanks

[@siddharthdubey9389]

Why did you add (2,2,3) to the priority queue when 2 was already visited? (seek the video to 8:50)

[@RituSharma-zp7xs]

Yeah same doubt, it shouldn't be added

[@artifice_abhi]

@@RituSharma-zp7xs won't have any effect tho ... he did it by mistake

[@hrushi_borhade]

Understood Striver!!

[@ky747r0]

great

[@sanketh768]

I think there's a mistake in TC calculation. getting the min element from minHeap which is peek or poll is O(1) and not O(E), at least in java Please correct me if i'm wrong

[@yashsingh3040]

Picking smallest elment is O(1) but he is removing it as well. so due to hipyification rearrangement of pq would take place resulting the time complexity of O(logE).

[@sanketh768]

@@yashsingh3040 got it now, thanks for the clarification

[@iamnoob7593]

@@sanketh768 Tc is suppose to be ElogE + (E)2logE

[@HardikJain_YT]

Lol the intuition was mix of prims and kruskal>! Prims would be 0-1 2-1 (2-4 or 2-3) then 4-3