G-45. Prim's Algorithm - Minimum Spanning Tree - C++ and Java
Vložit
- čas přidán 19. 06. 2024
- 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
---------------------------------------------------------------------------------------------------------------------------
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
thanks for your valuable content 🙂
understood ♨️
bhaiya notes link
Oh ho maje aa gye tree me to 😁. Thanks bhaiya
Understood understood understood 😊
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.
😹 lol having 3 lakh subs And Views 5-10 k I think paid Views Hain 😹😹😹
@@shivanshnamdev6417 Advanced topic itne hi log padhte hai. Waki log bas c aur java ka one shot hi deakh te rehte hai.
😹 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
@@ayushpatel2171 💀
@@shivanshnamdev6417 4 saal baad ana
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❤
Dhattarwal's videos are as useless as your linkedin posts.
Exactly!
that microsoft girl has also tought graph theory but that isnt worth it.she didnt discuss no ques. striver is best
i have been following u on linkedin
awesome content! i appreciate it
@@lakshsinghania thanks buddy
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
👍
Copy mein bana leta bhai
@@ayushanand5659 lol
I think 0 is not marked visited while pushing into the queue but when it is taken out of queue
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.
OOps sorry, yes
Yeah I watched it Second time and then noticed it😅 good point!
Paused the vdo...and searched for the comment which mentioned this
nice one i also observed this
Yea I was searching for this comment, why nobody pointed out the error. Got it!!
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
But what he said was right ?
@@pritammehta7770yeah. Maybe using a girl thumb line was wrong point but rest of the part is 100% right.
@@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
@@JohnWick-oj6bw kon critcise kr rha tha bhai ?🙄
Who is criticizing him and for what ? @@pritammehta7770
Striver bhaiya ignore these freshers
Bache hai samaj utna hai nhi
U just keep moving forward
Love you 100000❤❤❤❤
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 .
Striver is real teacher. And motivation for me
3million ka channel ek tweet ka reply karne ke liye video bana pada😂😂
Ye daar hona jaruri hai❤😂💯
@@MN-gn7lt tere behen ko koi Bolega na tab mat bolna
ye dar hame accha laga
Whoever criticizing striver you will know the quality of this man ,when you really start coding from heart
Who is criticizing him and for what ?
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.
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
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. 👍
Thankyou Striver for such a beautiful explanation ❤ and a Happy New Year ❤🎉
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.
But it was a bit complex, this is more straightforward and easy 😅
I too felt in the same way
It cleared almost all of the dought and got a very good intution .
U r the best ...no other content can ever be better then this one ..🥰🥰🥰🥰🥰🥰💌
Amazing explanation, thank you for teaching us.
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.
Understood and awesome as usual
Waiting for the next videos of this series!
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 .
Understood! :)
Thank you bhaiya! 🙏🏻😊
Thank You So Much for this wonderful video............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
thanks Striver for great playlist
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 .
Understood! Super awesome explanation as always, thank you very much!!
striver bhai today i understood prim's algorithm using ds priority queue to find minimum spanning tree thank you
Perfect as always ♥
Really good Explanation - Just one feedback, start with Intuition first then move forward with the algorithm instead of other way around.
Maja aa gaya bhayiya love your content
Best thing about him is that he emphasises on what we should not do. That's the way we remember it oo
God bless you bro ! You are taking too much effort to teach. This shows your dedication and passion 🔥🔥✨✨
I completely agree with you bhaiya.
Abhi Aman Aman kar rhe h sabhi, 3 saal ke baad yahi se placement k liye padhenge 😂
Bhai m 11th class m hun, iss bande ka content shi m achcha h kya? Abhi jee ki prep kar raha hun.
@@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..
ekdam sahi bat bole bhai...abhi fresher hai inko kya hi pata job lena kitta mushkil hai
Thank you striver
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
what should be Prim's then?
@@shreyanshagrawal3115 exactly!
no bro , both prim's kruskal are greedy , intuition for both are same we doing greedy in both cases .
Yeah I was confused at 16:24 since I don't think that edge (1,4,3) would be in the priority queue yet
Thanks striver!!!!
Understood 🙌
is this approach also same like finding shortest distance from source to destination since we are adding distances into the sum variable?
Understood bhaiya 🙏❤️
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
Striver=huge love+respect❤
Awesome 👏👏
this one is similar to Dijkstra's
Please make video on union find (DSU) questions... not able to solve leetcode ones
Thank you sir 😊
Understood Sir!
Understood 🔥🔥
understood💙
Understood!
Why did we take (2,2,3) at 8:45, we see before added if the node is already visited no? pls clarify
understood🔥🔥🔥
understood!
Understood✌️
Thank you so much for this video, could please also make the video on kruskal algorithm for this new playlist..??
Yes it will come soon.
understood :)
thanks man
Sir asking off topic question.......
What's your tech stack? Means which technology you are proficient?
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
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?
noh, we will follow similar approach in kruskal, you will see how to deal with it
Understood !!!
Thank you bhaiya
Understood:)
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
Thank you sirrrrrrr
Thanks 🐻❄🐻❄
what should i change to the code to get mst for example like this " {(0, 2), (1, 2), (2, 3), (3, 4)} "
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.
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
in djikstra it can consider more than n-1 edges
can we use this algorithm to find the shortest distance between two nodes
understood
plz make a video on question - max cashflow among friends
I think the adj nodes wala loop ,will run for 2E , ans no of adjnodes or neighbours in undirected graph is 2E
Sir make start array and strings series also please for interview purpose
understood bhaiya
You are still more than god for some people striver
Understood 😇
Understood
CP is incomplete without this guy
Is their will be more videos in this series ?
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.
Understood Bhaiya
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?
UNDERSTOOD
How many more videos will be coming regarding this topic?
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
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
Most of them are arts student man
@@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
@@JohnWick-oj6bw believe me I have an experience about who is fooling us and who is giving an authentic education .
great
Plz make vedion on :
Bridges in a graph
@8:44 node 2 should not be included in the priority queue as node 2 was already visited
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 😳😳😳
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😎
Teri behen ko koi ese hi bolega to tujhe chalega kya
People are toxic because of his thoughts are toxic
@@user-fz1yv4lq4d haan chal abhi apne kaksha meh ja ke bheth ja
@@MN-gn7lt ab Jada ro mt
#striver could u plzz cover LeetCode 1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree Problem... ???
Driver bhaiya aapke to maje hai yaar😁😁😁
actually better
Priority queue top element take O(logn) time ?
Can anybody tell why are we doing something like this ( ( x , y ) - > x.distance - y.distance ) in priority queue declaration in Java ?
Habibi ek aur mast bideo banaye ho
Same on u
I am very confused when to use a visited array and when not to use visited array. And also confused when a node is considered to be visited?
yes
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
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).
@@yashsingh3040 got it now, thanks for the clarification
@@sanketh768 Tc is suppose to be ElogE + (E)2logE