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
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
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❤
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
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
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.
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
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.
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.
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 😳😳😳
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
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
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..
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. 👍
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 .
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.)
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 .
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?
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).
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?
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.
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
Did't watch the video since we only need to traverse all nodes with minimum path so I directly use BFS with PQ...... I don't use dikastra here because dikastra may not include all if that node weight is bigger than someone else class Solution { static int spanningTree(int V, int E, List adj) { PriorityQueue pq = new PriorityQueue(Comparator.comparingInt(a -> a[1])); boolean[] visited = new boolean[V]; int mstWeight = 0; int edgesInMST = 0; pq.add(new int[]{0, 0}); while (!pq.isEmpty() && edgesInMST < V) { int[] edge = pq.poll(); int node = edge[0]; int weight = edge[1]; if (visited[node]) continue; visited[node] = true; mstWeight += weight; edgesInMST++; for (int[] neighbor : adj.get(node)) { int nextNode = neighbor[0]; int nextWeight = neighbor[1]; if (!visited[nextNode]) { pq.add(new int[]{nextNode, nextWeight}); } } } return mstWeight; } }
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 :)
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?
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!
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)); }
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
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
DOUBT ! DOUBT ! DOUBT ! while(!pq.empty()){ auto it = pq.top(); pq.pop(); int node = it.second; int edgewt=it.first;
if(vis[node]==1) continue;
vis[node]=1; sum+=edgewt; for(auto j: adj[node]){ int adjNode=j.first; int ewt=j.second; if(!vis[adjNode]){ pq.push({ewt,adjNode}); } } what does last 5 & 6 line means, as from first 4th & 5th line node = second part of adj pair and wt = first part of adj pair But in case of adjNode and ewt this is vice versa how and why??
Since the GFG has changed ths question a bit now , in argument adjacency matrix is given instead if adjacency list so you can take help from my code : class Triology{ int u; int v; int wt; Triology(int u,int v,int wt){ this.u=u; this.v=v; this.wt=wt; } } class Pair{ int v; int wt; Pair(int v,int wt){ this.v=v; this.wt=wt; } } class Solution{ static int spanningTree(int V, int E, int edges[][]){ List adj=new ArrayList(); for(int i=0;i
@@prakharsinha4145 because in priority queue you need to define the parameters on what basis you want to prioritise values, I have written x.wt-y.wt that is basically implemented using generics You can learn more about that by learning to override comparator function in Java
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 😊
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
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
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
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
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!!
Striver bhaiya ignore these freshers
Bache hai samaj utna hai nhi
U just keep moving forward
Love you 100000❤❤❤❤
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 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
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
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
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.
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
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 .
Really good Explanation - Just one feedback, start with Intuition first then move forward with the algorithm instead of other way around.
Best thing about him is that he emphasises on what we should not do. That's the way we remember it oo
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
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
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
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. 👍
U r the best ...no other content can ever be better then this one ..🥰🥰🥰🥰🥰🥰💌
CP is incomplete without this guy
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.
Amazing explanation, thank you for teaching us.
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❤❤❤❤❤❤❤
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 .
It cleared almost all of the dought and got a very good intution .
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.)
striver bhai today i understood prim's algorithm using ds priority queue to find minimum spanning tree thank you
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
what's the need of condition if(!vis[adjnode]) if we are already concern about if(vis[node]){
continue;
}
Waiting for the next videos of this series!
Please make video on union find (DSU) questions... not able to solve leetcode ones
thanks Striver for great playlist
Thank You So Much for this wonderful video............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
God bless you bro ! You are taking too much effort to teach. This shows your dedication and passion 🔥🔥✨✨
Thankyou Striver for such a beautiful explanation ❤ and a Happy New Year ❤🎉
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.
Driver bhaiya aapke to maje hai yaar😁😁😁
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 .
Maja aa gaya bhayiya love your content
Striver=huge love+respect❤
You are still more than god for some people striver
Understood and awesome as usual
Thank you sir 😊
Mil gya fame , driver bhaiya appko . 😅
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
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
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?
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! :)
Thank you 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?
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
Did't watch the video since we only need to traverse all nodes with minimum path so I directly use BFS with PQ...... I don't use dikastra here because dikastra may not include all if that node weight is bigger than someone else
class Solution {
static int spanningTree(int V, int E, List adj) {
PriorityQueue pq = new PriorityQueue(Comparator.comparingInt(a -> a[1]));
boolean[] visited = new boolean[V];
int mstWeight = 0;
int edgesInMST = 0;
pq.add(new int[]{0, 0});
while (!pq.isEmpty() && edgesInMST < V) {
int[] edge = pq.poll();
int node = edge[0];
int weight = edge[1];
if (visited[node]) continue;
visited[node] = true;
mstWeight += weight;
edgesInMST++;
for (int[] neighbor : adj.get(node)) {
int nextNode = neighbor[0];
int nextWeight = neighbor[1];
if (!visited[nextNode]) {
pq.add(new int[]{nextNode, nextWeight});
}
}
}
return mstWeight;
}
}
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
thanks for the great video
Understood! Super awesome explanation as always, thank you very much!!
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 :)
I completely agree with you bhaiya.
Lol the intuition was mix of prims and kruskal>!
Prims would be 0-1 2-1 (2-4 or 2-3) then 4-3
Awesome 👏👏
this one is similar to Dijkstra's
It's demotivating how quickly he codes it up with such ease... like bro we get atleast 4-5 bugs everytime
understood
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
@8:44 node 2 should not be included in the priority queue as node 2 was already visited
Understood bhaiya 🙏❤️
Can anybody provide the code where the parent will be considered
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
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!
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));
}
canu provide full code
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
plz make a video on question - max cashflow among friends
At 8:55 as 2 is already visited, (2,2,3) must not push into the pq
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
Why cant we mark the node as vis while pushing into the priority queue
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.
I think the adj nodes wala loop ,will run for 2E , ans no of adjnodes or neighbours in undirected graph is 2E
Understood!
is this approach also same like finding shortest distance from source to destination since we are adding distances into the sum variable?
Can anybody tell why are we doing something like this ( ( x , y ) - > x.distance - y.distance ) in priority queue declaration in Java ?
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
can we use this algorithm to find the shortest distance between two nodes
Thank you striver
Understood 😊
Perfect as always ♥
Understood 🔥🔥
DOUBT ! DOUBT ! DOUBT !
while(!pq.empty()){
auto it = pq.top();
pq.pop();
int node = it.second;
int edgewt=it.first;
if(vis[node]==1) continue;
vis[node]=1;
sum+=edgewt;
for(auto j: adj[node]){
int adjNode=j.first;
int ewt=j.second;
if(!vis[adjNode]){
pq.push({ewt,adjNode});
}
}
what does last 5 & 6 line means, as from first 4th & 5th line node = second part of adj pair and wt = first part of adj pair But in case of adjNode and ewt this is vice versa how and why??
if u do figure it out, let me know
because priority_queue stores in format {dis,node} and adjList is storing in format {adjNode,edW};.
Understood 🙌
My learning Flow
RECURSION
BACKTRACKING
TREES
GRAPHS
DP
ALL ARE CONNECTED IF U MISS THE ORDER THEN IT WILL
Prims algo always start with least edge weight not random
Haa bhaiyyy DRIVER OP😂😂. Be prepared bro. Now your channel will grow ultimately. After apna cllg. Video.what a Smart move😂😂😂.
Congrats, u helped him grow even more. 🤣
He doesn't need thumbnail waali ldki now 😂
Understood Sir!
Understood
Since the GFG has changed ths question a bit now , in argument adjacency matrix is given instead if adjacency list
so you can take help from my code :
class Triology{
int u;
int v;
int wt;
Triology(int u,int v,int wt){
this.u=u;
this.v=v;
this.wt=wt;
}
}
class Pair{
int v;
int wt;
Pair(int v,int wt){
this.v=v;
this.wt=wt;
}
}
class Solution{
static int spanningTree(int V, int E, int edges[][]){
List adj=new ArrayList();
for(int i=0;i
thanks for your help
Can you plzz tell why are we doing something like this ( ( x , y ) - > x.wt - y.wt ) in priority queue declaration in Java ?
@@prakharsinha4145 because in priority queue you need to define the parameters on what basis you want to prioritise values, I have written x.wt-y.wt that is basically implemented using generics
You can learn more about that by learning to override comparator function in Java
Since we require only two parameters v and wt, so why it is reqired to take three attribute in Triology class.
@@it_91_vaibkhare20well it depends, you can aslo do it with 2 parameters only 👍
Sir asking off topic question.......
What's your tech stack? Means which technology you are proficient?
if you watch jenny lecture and combine the intution part here it would be excellent