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
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.
😹 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
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
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 ?
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.
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
@@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
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 .
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
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❤️
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.
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
@@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..
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
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. 👍
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)
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.)
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 😳😳😳
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 .
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.
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 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
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 .
14:10 sir, in vectoradj[ ] given in ques, inner vector should store int, not pair how does it work for it[0] or it[1] in code, as it should have been vector
cause when adjacency list was made it was stored in that order ex : adj[node1] = {node 2, wt. b/w nodes}. But when using priority queue we want it sorted according to weight that's why in pq we push wt first then node. Hope it Helps!
I am not getting the time complexity outer while will be E and for inside ElogE for for loop and for pq.pop(); log E so it should be E( log E + ElogE) so it should be ElogE +E I am assuming this right ?? Or anything else?
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).
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.
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?
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?
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
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 :)
Prim's Algorithm builds the Minimum Spanning Tree (MST) by adding the minimum weight edge that connects a node inside the MST to a node outside it. Visited Array in Prim's: The visited array is used to ensure that once a node is added to the MST, it is not considered again. This is because, in an MST, each node is included exactly once, and revisiting it would contradict the tree structure, potentially leading to cycles or incorrect results. Key Point: Once a node is part of the MST, all further edges leading to it are ignored (using the visited array). This is because in an MST, every node is connected by exactly one path, ensuring a tree structure. Dijkstra's Algorithm finds the shortest path from a source node to all other nodes. No Visited Array in Dijkstra's (Common Implementation): In Dijkstra's algorithm, we do not necessarily use a visited array in the traditional sense like in Prim's. Instead, nodes are revisited whenever a potentially shorter path to that node is found. The priority queue (min-heap) ensures that the shortest known path is processed first. Key Point: Nodes can be revisited in Dijkstra's algorithm because the algorithm continually checks if there is a shorter path to each node. The priority queue processes the shortest path available at any time, which may lead to revisiting a node if a shorter path is discovered.
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
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
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
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 ?
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 .
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.
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 ?
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
Really good Explanation - Just one feedback, start with Intuition first then move forward with the algorithm instead of other way around.
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❤️
Should i learn Java aur c++ for this
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.
@@study8 C++ is better for this
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
Best thing about him is that he emphasises on what we should not do. That's the way we remember it oo
you are amazing striver, wish to meet you someday !!
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
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
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.
U r the best ...no other content can ever be better then this one ..🥰🥰🥰🥰🥰🥰💌
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
CP is incomplete without this guy
Driver bhaiya aapke to maje hai yaar😁😁😁
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
Why did we take (2,2,3) at 8:45, we see before added if the node is already visited no? pls clarify
shouldn't be added mistake
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
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. 👍
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)
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.)
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❤❤❤❤❤❤❤
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
It cleared almost all of the dought and got a very good intution .
understood, really nice way of explanation . i got it in one shot.👍
Thank You So Much for this wonderful video............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Striver=huge love+respect❤
Amazing explanation, thank you for teaching us.
thanks Striver for great playlist
striver bhai today i understood prim's algorithm using ds priority queue to find minimum spanning tree thank you
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 .
Waiting for the next videos of this series!
Thankyou Striver for such a beautiful explanation ❤ and a Happy New Year ❤🎉
You are still more than god for some people striver
Maja aa gaya bhayiya love your content
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.
They know, all the nalla berozgar are feminists.
And will spread toxicity, so he xan continue fooling students.
God bless you bro ! You are taking too much effort to teach. This shows your dedication and passion 🔥🔥✨✨
Mil gya fame , driver bhaiya appko . 😅
Thank you sir 😊
Understood and awesome as usual
Understood bhaiya 🙏❤️
Understood! :)
Thank you bhaiya! 🙏🏻😊
Awesome 👏👏
this one is similar to Dijkstra's
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.
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 .
Why did you add (2,2,3) to the priority queue when 2 was already visited? (seek the video to 8:50)
Yeah same doubt, it shouldn't be added
@@RituSharma-zp7xs won't have any effect tho ... he did it by mistake
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 .
14:10 sir, in vectoradj[ ] given in ques, inner vector should store int, not pair how does it work for it[0] or it[1] in code, as it should have been vector
Please make video on union find (DSU) questions... not able to solve leetcode ones
at 17:20 why pq.top() takes O[log(v)] time complexity , it takes O(1) constant time since it is on top of priority_queue ????????
.top() is indeed O(1), .push() and .pop() takes O[log(v)]
Understood! Super awesome explanation as always, thank you very much!!
why adjnode=i[0] not i[1] at 13:49
cause when adjacency list was made it was stored in that order ex : adj[node1] = {node 2, wt. b/w nodes}.
But when using priority queue we want it sorted according to weight that's why in pq we push wt first then node.
Hope it Helps!
@8:44 node 2 should not be included in the priority queue as node 2 was already visited
Lol the intuition was mix of prims and kruskal>!
Prims would be 0-1 2-1 (2-4 or 2-3) then 4-3
I am not getting the time complexity outer while will be E and for inside ElogE for for loop and for pq.pop(); log E so it should be E( log E + ElogE) so it should be ElogE +E I am assuming this right ?? Or anything else?
At 8:55 as 2 is already visited, (2,2,3) must not push into the pq
what's the need of condition if(!vis[adjnode]) if we are already concern about if(vis[node]){
continue;
}
Perfect as always ♥
Understood 🔥🔥
I completely agree with you bhaiya.
I think the adj nodes wala loop ,will run for 2E , ans no of adjnodes or neighbours in undirected graph is 2E
It's demotivating how quickly he codes it up with such ease... like bro we get atleast 4-5 bugs everytime
Habibi ek aur mast bideo banaye ho
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).
@@YashSin2025 got it now, thanks for the clarification
@@sanketh768 Tc is suppose to be ElogE + (E)2logE
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.
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?
thats what i m thinking
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?
Thank you striver
UNDERSTOOD!!
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
thanks for the great video
Sir asking off topic question.......
What's your tech stack? Means which technology you are proficient?
Understood 🙌
Understood✌️
Understood Bhaiya
is this approach also same like finding shortest distance from source to destination since we are adding distances into the sum variable?
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
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
Standing at node 3, why are adding node 2 in the PQ ? I think that's a mistake. It was already visited!
yes its a mistake by striver over there
@@lakshsinghania yesssss
Understood Sir!
Understood Striver!!
Thanks striver!!!!
lage raho driver bhai😂😂
Has le , abhi baccha hai 2-3 saal baad yahi se padhega
@@sandeepsuman6381 naa bhaiii humm too apna college se pdenge
@@navneetsingh2274 mujhe controversy ka to pta nhi kya hua , lekin apna college ka content comparable bhi nahi hai abhi striver se
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 :)
what should i change to the code to get mst for example like this " {(0, 2), (1, 2), (2, 3), (3, 4)} "
Thank you bhaiya
understood bhaiya
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?
Prim's Algorithm builds the Minimum Spanning Tree (MST) by adding the minimum weight edge that connects a node inside the MST to a node outside it.
Visited Array in Prim's: The visited array is used to ensure that once a node is added to the MST, it is not considered again. This is because, in an MST, each node is included exactly once, and revisiting it would contradict the tree structure, potentially leading to cycles or incorrect results.
Key Point: Once a node is part of the MST, all further edges leading to it are ignored (using the visited array). This is because in an MST, every node is connected by exactly one path, ensuring a tree structure.
Dijkstra's Algorithm finds the shortest path from a source node to all other nodes.
No Visited Array in Dijkstra's (Common Implementation): In Dijkstra's algorithm, we do not necessarily use a visited array in the traditional sense like in Prim's. Instead, nodes are revisited whenever a potentially shorter path to that node is found. The priority queue (min-heap) ensures that the shortest known path is processed first.
Key Point: Nodes can be revisited in Dijkstra's algorithm because the algorithm continually checks if there is a shorter path to each node. The priority queue processes the shortest path available at any time, which may lead to revisiting a node if a shorter path is discovered.
can we use this algorithm to find the shortest distance between two nodes
understood💙
Understood 😇
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
Sir make start array and strings series also please for interview purpose
Plz make vedion on :
Bridges in a graph