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

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

[@43johri]

In BFS also, you can do same thing. First add it to the queue, and once popped, mark it visited and continue. What do you think is wrong with this approach ?

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

[@WhyYouN00B]

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

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

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

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

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

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

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

[@aniruddhadas1778]

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❤️

[@study8]

Should i learn Java aur c++ for this

[@pradeepkumarbishnoi8127]

Dehk bhai tuje iska acha lag ta hai tu iska dehk. Muje jo jada samj ayaga ma uska dehkuga. To isma nahi hi tu galat hai or na hi main.

[@JohnWick-oj6bw]

@@study8 C++ is better for this

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

[@shashankjoshi8250]

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

[@AashiSaxena-g8z]

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

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

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

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

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

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

[@nishant1456]

CP is incomplete without this guy

[@preranapatro2414]

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

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

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

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

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

[@codingkrtehum..]

understood, really nice way of explanation . i got it in one shot.👍

[@lonerider6695]

basically pq is ensuring that we get min distance from source to each node and vis array is making sure all that all nodes are visited And carefully observing these two are the only conditions for a MST i.e. min dis (done by pq) and all node are connected (vis array taking care of that)

[@AtharvaRao0104]

PQ will only have crossing edges. and it gives the min weight edge when asked ..this will ultimately ensure you build a MST .. visited array is to keep the vertices already in the MST. And at the end, all vertices have to be in the MST. (and V-1 Edges also will be in MST.)

[@keepitup3077]

Driver bhaiya aapke to maje hai yaar😁😁😁

[@saibunny1253]

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

[@funnyanimation888]

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

[@dhruvsolanki4473]

Amazing explanation, thank you for teaching us.

[@rishav144]

thanks Striver for great playlist

[@shigoeditz7079]

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

[@h108pranavshinde3]

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

[@raghavagrawal9240]

Waiting for the next videos of this series!

[@stith_pragya]

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

[@bhadanavikas_13]

Why people commenting so much toxicity about him what's his fault ? He's right 💯 in very instances, firstly, for all who comments toxicity about him ( like driver bahiya etc ), first of all read his all tweets and information that he point about apna college team deeply , You (students ) are Aman dhatarwal fan is not the reason ki tum uski koi buri cheez ko point out nhi kroge . Same on you 😳😳😳

[@MN-gn7lt]

Guys twitter pe jo accha kaam kiya hai striver ne woh daalo unko bhi toh pata chale ki ye jiska course shikhate hai ye bhandha uss chez ka GOD hai😎

[@user-fz1yv4lq4d]

Teri behen ko koi ese hi bolega to tujhe chalega kya

[@user-fz1yv4lq4d]

People are toxic because of his thoughts are toxic

[@MN-gn7lt]

@@user-fz1yv4lq4d haan chal abhi apne kaksha meh ja ke bheth ja

[@user-fz1yv4lq4d]

@@MN-gn7lt ab Jada ro mt

[@simmi641]

Striver=huge love+respect❤

[@VIVardhan5130]

You are still more than god for some people striver

[@krishanpratap3286]

Maja aa gaya bhayiya love your content

[@harshjoshi5888]

Hello bhai want to tell you something serious .yeh jo aapke channel mein comments ho rhe hain unpe bilkul dhyan math Dena they are not college students they are so called jee neet aspirants who don't want to study for themselves but want themselves to be a saviour of their so called teachers .they are toxic fans of their teachers who don't want their students to think practically but let them to think only emotionally . Leave them aside we were with you and always . Please pin my comment because this is really serious

[@JohnWick-oj6bw]

Most of them are arts student man

[@harshjoshi5888]

@@JohnWick-oj6bw not arts students bro they science students only and call themselves an aspirant yeh log poore saal bhaiya didi hi karte rehte hain main isliye yeh sab kh paa rha hoo kyuki do saal pehle main jis institute mein tha in online for jee coaching yeh sab vha aake teachers ko galiyan dete the ki tumhari toh fees itni jyada h vgrh

[@harshjoshi5888]

@@JohnWick-oj6bw believe me I have an experience about who is fooling us and who is giving an authentic education .

[@sarangs722]

Apna College's content isn't that good. So, now they have resorted to attacking with playing the petty "women victim card". Striver, we love you bro. Your content is clearly better than that channel's content. Keep going! We are here with you.

[@JohnWick-oj6bw]

They know, all the nalla berozgar are feminists. And will spread toxicity, so he xan continue fooling students.

[@udaytewary3809]

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

[@cinime]

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

[@UECAshutoshKumar]

Thank you sir 😊

[@sukhpreetsingh5200]

Understood and awesome as usual

[@varunakrishnani7688]

Understood! :) Thank you bhaiya! 🙏🏻😊

[@Rajat_maurya]

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

[@tanishkumar5440]

Mil gya fame , driver bhaiya appko . 😅

[@amitp277]

Awesome 👏👏 this one is similar to Dijkstra's

[@CodeMode9313]

Habibi ek aur mast bideo banaye ho

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

[@euvsielr]

I completely agree with you bhaiya.

[@vaalarivan_p]

2:10 - 6:57

[@Stellar_7x]

UNDERSTOOD!!

[@ARNAVGUPTA-s1m]

In the end, while explaining the intuition for the Algorithm, you gave the explanation for the Kruskal's algorithm by mistake. The Prim's Algorithm works on the fact that we try to add unvisited nodes to our MST, but we search for the new nodes through a greedy approach of looking at the minimum weighted edges first. Actually, the difference between the Algorithms is very subtle. For Kruskals: we look at smallest edges, and then check if it is a new node. Prim's: we are increasing our MST by adding new nodes, by looking at the smallest edge option from the nodes we already have visited.

[@mriduljain6809]

Understood Bhaiya

[@hrushi_borhade]

Understood Striver!!

[@hardikjain-brb]

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

[@gangsta_coder_12]

Understood 🔥🔥

[@shauryatomer1058]

thanks for the great video

[@aayushojha3088]

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

[@parshchoradia9909]

Understood Sir!

[@Learnprogramming-q7f]

Thank you bhaiya

[@aniruddhadas1778]

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

[@abhijeetmishra3804]

understood bhaiya

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

[@mihirsaini592]

Thank you striver

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

[@priyanshgarg1292]

shouldn't be added mistake

[@amanbhagat1616]

I think time complexity is - E(log E + E Log E) =~ E^2 Log E ? [1]Outer while loop running E times at max (as explained in video) [2] Inside while pop from Heap (or Priority Queue) would take up Log E (as explained in video) [3] Iterating over neighbors and adding them to Priority Queue taking E log E (as explained in video) So, overall time complexity should be E^2 Log E ? isn't it? does anyone thinks the same?

[@utkarshiitbhu4204]

thats what i m thinking

[@itz_me_imraan02]

Perfect as always ♥

[@ACUCSPRADEEPB-up9ne]

Understood✌️

[@infinite9953]

Understood 🙌

[@adebisisheriff159]

Thanks striver!!!!

[@surjendupal7576]

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

[@just.subhan.]

Haa bhaiyyy DRIVER OP😂😂. Be prepared bro. Now your channel will grow ultimately. After apna cllg. Video.what a Smart move😂😂😂.

[@JohnWick-oj6bw]

Congrats, u helped him grow even more. 🤣 He doesn't need thumbnail waali ldki now 😂

[@jaishriharivishnu]

int spanningTree(int V, vector adj[]) { // distance, node, parent priority_queuepq; // initially take node 0 vectorvis(V); vis[0]=1; for(auto K:adj[0]){ pq.push({K[1],K[0],0}); } vectoredges; // weight, node , node // edges are the edges that will be in the MST while(!pq.empty()){ auto cur=pq.top(); pq.pop(); int curnode=cur[1]; int parent=cur[2]; int curdistance=cur[0]; if(!vis[curnode]){ vis[curnode]=1; edges.push_back(cur); for(auto K:adj[curnode]){ int childnode=K[0]; int childdistance=K[1]; if(!vis[childnode]){ pq.push({K[1],childnode,curnode}); } } } } int answer=0; for(auto K:edges){ answer+=K[0]; } return answer; } code for GFG.... NOTE: this also include the all the edges of the MST :)

[@prakashnandan7337]

At 8:55 as 2 is already visited, (2,2,3) must not push into the pq

[@dharmenderkumar2841]

UNDERSTOOD

[@ShivamYadav-xx6oc]

lage raho driver bhai😂😂

[@sandeepsuman6381]

Has le , abhi baccha hai 2-3 saal baad yahi se padhega

[@navneetsingh2274]

@@sandeepsuman6381 naa bhaiii humm too apna college se pdenge

[@justarandomguy6106]

@@navneetsingh2274 mujhe controversy ka to pta nhi kya hua , lekin apna college ka content comparable bhi nahi hai abhi striver se

[@amanbhadani8840]

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

[@2amCoder]

for java folks who is facing problem ArrayList adjList = new ArrayList(); for (int i = 0; i < V; i++) { adjList.add(new ArrayList()); } for (int i = 0; i < E; i++) { int u = edges[i][0]; int v = edges[i][1]; int weight = edges[i][2]; adjList.get(u).add(new Pair(weight, v)); adjList.get(v).add(new Pair(weight, u)); }

[@avvarunithinvenkatasaisank5964]

canu provide full code

[@TarunKumarSaraswat]

thanks

[@hardikjain-brb]

actually better

[@ujjwalraj9837]

It's demotivating how quickly he codes it up with such ease... like bro we get atleast 4-5 bugs everytime

[@priyanshvatsal9791]

Understood 😇

[@hope-jh7bv]

understood💙

[@sumitnagar8367]

what's the need of condition if(!vis[adjnode]) if we are already concern about if(vis[node]){ continue; }

[@_MS98]

Thanks 🐻‍❄🐻‍❄

[@debajyatibanerjee5480]

Understood!

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

[@Maddy_ke_Papa]

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]

@@Maddy_ke_Papa got it now, thanks for the clarification

[@iamnoob7593]

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

[@iWontFakeIt]

mic quality >>>>

[@SurajSharma-z9p]

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?

[@23ritik]

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

[@akashsahu2571]

yes

[@Now_I_am_all_fired_up]

Plz make vedion on : Bridges in a graph

[@pratikgaikar9383]

Prims algo always start with least edge weight not random

[@SadhanaSharma]

Thank you sirrrrrrr

[@dinakarrajkotipalli2250]

if you watch jenny lecture and combine the intution part here it would be excellent