Dijkstra : from a single source, find shortest paths to all nodes. Floyd-Warshall : shortest path from every node as a source. Bellman-Ford : same as Dijkstra, but works for negative weights. Topological Sort : print the nodes with no incoming edges first. MST : connect all the nodes with minimum costs (n nodes // n-1 edges). Prim's Algo : build the MST by starting from any node and expanding the tree one edge at a time. Kruskal Algo : build the MST by sorting all edges and adding them one by one, ensuring no cycles are formed.
I'd like to add on to Bellman Ford and Dijkstra Dijkstra: Works on both directed and undirected graph with non-negative edge weights, Greedy approach Bellman Ford: Works on both directed and undirected graph with non-negative edge weights as well as directed graph with negative edge weights as long as no negative cycles are present, Dynamic Programming approach
Thanks Striver! I was solving a leetcode problem and unable to solve it then i saw the topic was Disjoint set and I watched these few videos and instantly recognized that the problem can be solved using Kruskal's Algorithm easily
T.C ->Summing up the above steps: O(E)(building edges vector)+O(E⋅logE)(sorting edges)+O(E⋅α(V))(union-find operations)==>TC: O(E⋅logE). Space Complexity: O(V+E)
Why cant we just have some added array(like visited array) where we check if a node has already been added to the tree we are constructing? , do we really need disjoint set for this? Or am i missing something?
according to code: parent[ulp_v] = ulp_u; but at timestamp 05:30 we are attaching node 6 to node 2, shouldn't 6 gets attached to ultimate parent of 2 i.e. 1 instead ?
I have a question. How to write code of the program to calculate/print all spanning trees of a graph? If anyone can help me with the code I shall be obliged🙏🙏
Give more info Does the graph have all nodes connected to one another? If so then you would need to find the positions where two different edges with the same weight connect to the new node then you can create two minimum spanning trees here and if you again find this position then there will be 4 and so on
Next time you are going to union by size for that same edge, the two nodes are already in the same component which is why the first check of making sure if the given two nodes are in same component or not which tells "you are already in one part just go - no need to do anything"
maybe initializing a priority queue of min heap to store the weights along with the node and the adjacent node would be better than to store them in a vector and later sort them?? correct me if I'm wrong?
It's giving TLE when Min Heap is used. Maybe because of using top and pop while creating the disjoint set which takes O(logN) compared to O(1) when we use a Vector.
How come time complexity is O(N+E) for the first loop? because outer will run for V that is num of nodes and inner auto with the number of nodes attached to it
The next edge selection in Kruskal's is NOT always an incremental extension of the current MST path (like in Prim's it's 1 visited and 1 non-visited). The selection criteria here is just the next shortest edge weight and NO cycle). The selected edge need not even meet the MST path selected so far and hence result in 2 disconnected components. Similarly there could be many more disconnected components. Now when the edge which merges these components is selected, both the vertex are sort of visited... so how do you differentiate if it causes a cycle or its the 2 components merging?. Having just 2 arrays - visited and unvisited won't help. You'll require 1 array for unvisited, and as many separate visited arrays as there are different components. All this leads to just using a Disjoint set.
def find(self,u): if u == self.parent[u]: return u
self.parent[u] = self.find(self.parent[u]) return self.parent[u] class Solution:
#Function to find sum of weights of edges of the Minimum Spanning Tree. def spanningTree(self, V, adj): edges = [] for i in range(V): for u , wt in adj[i]: edges.append([i,u,wt])
edges.sort(key = lambda x : x[2])
ds = UnionFind(V)
res = 0 for u , v , wt in edges: if ds.find(u) != ds.find(v): res += wt ds.union(u,v)
Simple Approach:- class Solution{ static int spanningTree(int V, int E, int edges[][]){ Arrays.sort(edges, new Comparator() { @Override public int compare(final int[] entry1, final int[] entry2) { final int x = entry1[2]; final int y = entry2[2]; return Integer.compare(x, y); } }); DisjointSet ds = new DisjointSet(V); int mstwt = 0; for(int i = 0; i
Same Time complexity , to form min Heap and sort but using min heap once again we have to perform logE times to extract minimum in sorting there's no need so sort is better TLDR; sorting E+ElogE and minheap ElogE + ElogE
If 2 is connected to 4, It is not the minimum spanning tree and according to disjoint set, the ultimate parent of 4 is 1 and ultimate parent for 2 is 2 itself. 1 size(=2) is greater than 2 size(=1), which is why 2 is connected to 1.
Firstly the number of times we are checking the ultimate parent is same as the number of edges so it is M*4*alpha. Second, both the findUPar and UnionBySize is executing simultaneously that's why 2 is getting mutltiplied. This simultaneous execution will be very less but for safety reasons we are multiplying 2 .
How tough is it to understand loops, if you are reading graphs, you should have that thing to read code in any language, cpp and java hardly have much difference. Learn to understand logic, codes can follow. Else you will be struggling in your job with so much of spoon feeding. The code is there, just read it mate. And understand the cpp explanation. It runs parallely
That's what we are doing in findParent(). Whenever we insert a node to a set of nodes, the parent of the inserted node will change. So everytime we needa use findParent() func
code for someone who does not find declaring class , intuitive in exams int findpar(int &a,vector &parent) { if(a==parent[a]) { return a; } return parent[a] = findpar(parent[a],parent); } int spanningTree(int V, vector adj[]) { vector parent(V); for(int i=0;i
Here is java code of gfg practise link class Solution { static class DisjointSet { List rank = new ArrayList(); List parent = new ArrayList(); public DisjointSet(int n) { for (int i = 0; i
java kruskal algorithm, creating edges list from adjacency list class Solution{ static class DisJointSetSize { // UNION BY SIZE; MORE INTUITIVE; KRUSKAL ALGORITHM SUBMITTED AND TESTED for gfg List parent = new ArrayList(); List size = new ArrayList(); public DisJointSetSize(int n) { for (int i = 0; i a[2] - b[2]); DisJointSetSize dsu = new DisJointSetSize(V); int sum = 0; for (int[] edge : edges) { int u = edge[0]; int v = edge[1]; int weight = edge[2]; if (dsu.findUltimateParent(u) != dsu.findUltimateParent(v)) { dsu.unionBySize(u, v); sum += weight; } } return sum; } }
Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too,.
Do follow me on Instagram: striver_79
I am not getting what the M and N stands for, when you are calculating time complexities.
understood
Dijkstra : from a single source, find shortest paths to all nodes.
Floyd-Warshall : shortest path from every node as a source.
Bellman-Ford : same as Dijkstra, but works for negative weights.
Topological Sort : print the nodes with no incoming edges first.
MST : connect all the nodes with minimum costs (n nodes // n-1 edges).
Prim's Algo : build the MST by starting from any node and expanding the tree one edge at a time.
Kruskal Algo : build the MST by sorting all edges and adding them one by one, ensuring no cycles are formed.
Thanks for this and it's very useful
I'd like to add on to Bellman Ford and Dijkstra
Dijkstra: Works on both directed and undirected graph with non-negative edge weights, Greedy approach
Bellman Ford: Works on both directed and undirected graph with non-negative edge weights as well as directed graph with negative edge weights as long as no negative cycles are present, Dynamic Programming approach
@@chetanraghavv Thanks
you will be remembered in all three tenses i.e past, current, future., keep going bro, my power to you.
Understood each and every second of the video. Thanks Striver.
Thanks Striver! I was solving a leetcode problem and unable to solve it then i saw the topic was Disjoint set and I watched these few videos and instantly recognized that the problem can be solved using Kruskal's Algorithm easily
when you said drivers code muje kuch yaad aaa gaya 😂😂🔥🔥 but yeah you are rider the dsa driver the one and only strive 😎😎
bhai kehna kya chhata hai ?
@@aakashgoswami2356 controversy ki baat kr rha h bhai vo but striver is best teacher for dsa learning
@@vishnubanjara5209 i still didnt get it
AWESOME! Loved it how he build concept from Disjoint sets.
Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Was waiting for the series to continue! Thanks
Understood! Super wonderful explanation as always, thank you!!
The logic kind of is if you join the edge with the same ultimate parent it would cause a cycle which is not allowed
Yeah!!
Bhai indeed the best teacher
Understood bhaiya 🙏❤️
Understood!
Super wonderful explanation❤
I solved this by myself after learning DSU, can I say I'm also a co-inventor of Kruskal's algortihm.
genius 😅
Understood Raj bhaiyaa ❤❤
Superb Explanations... ❤👏
T.C ->Summing up the above steps:
O(E)(building edges vector)+O(E⋅logE)(sorting edges)+O(E⋅α(V))(union-find operations)==>TC: O(E⋅logE).
Space Complexity: O(V+E)
One goog thing about krushkal is even you have multiple components , it can form MST in all those components
understood,great explanation
Why cant we just have some added array(like visited array) where we check if a node has already been added to the tree we are constructing? , do we really need disjoint set for this? Or am i missing something?
Please also make video on dp on trees, heavy light decomposition.
why not added both direction edges?
Fully understood bhaiya...
understood, thanks raj
Thank you sir 🙏
well explained sir. Understood clearly!
Understood Bhaiya❣
understood striver.... Thank you so much
according to code: parent[ulp_v] = ulp_u; but at timestamp 05:30 we are attaching node 6 to node 2,
shouldn't 6 gets attached to ultimate parent of 2 i.e. 1 instead ?
I have a question.
How to write code of the program to calculate/print all spanning trees of a graph?
If anyone can help me with the code I shall be obliged🙏🙏
Edges print krna hai jo ki part hai mst ka
Give more info
Does the graph have all nodes connected to one another?
If so then you would need to find the positions where two different edges with the same weight connect to the new node then you can create two minimum spanning trees here and if you again find this position then there will be 4 and so on
very nice explanation
Understood :)
Sep'5, 2023 12:03 am
Advice to self: I guess I will need to revise again after week and month; seems Tricky
why will the disjoint set ignore the undirected edges in the adjacency list? why will only one edge be considered in disjoint set?
Next time you are going to union by size for that same edge, the two nodes are already in the same component which is why the first check of making sure if the given two nodes are in same component or not which tells "you are already in one part just go - no need to do anything"
Understood clearly!!!!
how do you calculated time complexity it's typical to understand
Can we use priority queue here, instead of sorting the vector?
understood thanks sir ❣❣❣❣
Understood Striver thanks
class Disjointset
{
vectorrank,parent;
public:
Disjointset(int n)
{
rank.resize(n+1,0);
parent.resize(n+1);
for(int i=1;i
solved by my self
what is aplha???i have forgotten about it.....can anyone explain it??
its value is nearly 1
maybe initializing a priority queue of min heap to store the weights along with the node and the adjacent node would be better than to store them in a vector and later sort them?? correct me if I'm wrong?
It's giving TLE when Min Heap is used. Maybe because of using top and pop while creating the disjoint set which takes O(logN) compared to O(1) when we use a Vector.
Understood 👍🏻
How come time complexity is O(N+E) for the first loop? because outer will run for V that is num of nodes and inner auto with the number of nodes attached to it
yes u r right , in the worst case graph can be a complete graph and in that case for every node we have to run inner loop for n-1 times
@@6mahine_mein_google so how its time complexity is N+E
So which method is efficient for finding mst krushkal's or prim's
Both appears to have same TC
Understood Sir!
Thanks🙌
Understood❤
understood❤
understood bhaiya
understood sir
why are we not using visited array concept where if both vertex are visited we ignore the edge as it is making a loop
good idea, have you tried solving using this way
The next edge selection in Kruskal's is NOT always an incremental extension of the current MST path (like in Prim's it's 1 visited and 1 non-visited). The selection criteria here is just the next shortest edge weight and NO cycle). The selected edge need not even meet the MST path selected so far and hence result in 2 disconnected components. Similarly there could be many more disconnected components. Now when the edge which merges these components is selected, both the vertex are sort of visited... so how do you differentiate if it causes a cycle or its the 2 components merging?. Having just 2 arrays - visited and unvisited won't help. You'll require 1 array for unvisited, and as many separate visited arrays as there are different components. All this leads to just using a Disjoint set.
Understood 👏
cant we directly sort adj list??? Why do we have to make vector edges?
we could have used same edges array in solution to add to List right, why was the adjacency list created
Understood
Understood.
Python :
```
class UnionFind:
def __init__(self,n):
self.parent = [i for i in range(n)]
self.size = [1 for i in range(n)]
def union(self,u,v):
parent_u = self.find(u)
parent_v = self.find(v)
if parent_u == parent_v:
return True
if self.size[parent_u] < self.size[parent_v]:
self.parent[parent_u] = parent_v
self.size[parent_v] += self.size[parent_u]
else:
self.parent[parent_v] = parent_u
self.size[parent_u] += self.size[parent_v]
return False
def find(self,u):
if u == self.parent[u]:
return u
self.parent[u] = self.find(self.parent[u])
return self.parent[u]
class Solution:
#Function to find sum of weights of edges of the Minimum Spanning Tree.
def spanningTree(self, V, adj):
edges = []
for i in range(V):
for u , wt in adj[i]:
edges.append([i,u,wt])
edges.sort(key = lambda x : x[2])
ds = UnionFind(V)
res = 0
for u , v , wt in edges:
if ds.find(u) != ds.find(v):
res += wt
ds.union(u,v)
return res
```
Thanks bro
Great Video as Always..!
babbar bhaiya ne graph k naam pe kaat diya hain
btw this video is not yet updated with Striver SDE Sheet, had to search up this manually!!
UNDERSTOOD
understood!!!
when he said for java people i am like😎
understood!
Simple Approach:-
class Solution{
static int spanningTree(int V, int E, int edges[][]){
Arrays.sort(edges, new Comparator() {
@Override
public int compare(final int[] entry1, final int[] entry2) {
final int x = entry1[2];
final int y = entry2[2];
return Integer.compare(x, y);
}
});
DisjointSet ds = new DisjointSet(V);
int mstwt = 0;
for(int i = 0; i
We can use min heap instead of sorting the vector.
Same Time complexity , to form min Heap and sort
but using min heap once again we have to perform logE times to extract minimum
in sorting there's no need so sort is better
TLDR; sorting E+ElogE and minheap ElogE + ElogE
Understood !
thanks sir
why do we need bidirectional AL in here? unidirectional also gives same results
Mast hai bhai
but in code we were connecting ultimate parent of u with v, why are we connecting with u and v?
why is the *2 used in time complexity
Can anyone tell me why 2 is connected to 1, it should be connected to 4, according to the disjoint set?
If 2 is connected to 4, It is not the minimum spanning tree and according to disjoint set, the ultimate parent of 4 is 1 and ultimate parent for 2 is 2 itself. 1 size(=2) is greater than 2 size(=1), which is why 2 is connected to 1.
understood
Why twice the (Mx4xalpha)? Please let me know if I am wrong, but It should be (M+N) x4x alpha because we are making the union N-1 times.
Firstly the number of times we are checking the ultimate parent is same as the number of edges so it is M*4*alpha.
Second, both the findUPar and UnionBySize is executing simultaneously that's why 2 is getting mutltiplied. This simultaneous execution will be very less but for safety reasons we are multiplying 2 .
We have to write this whole DisjointSet class everytime for this type of questions?💀💀
Have to write disjoint code💀💀
Understood:)
No one can match striver energy and research for every video .........
On GFG this approach is giving TLE can someone help me to understand
understood :)
Can you please explain Java code also along with C++
How tough is it to understand loops, if you are reading graphs, you should have that thing to read code in any language, cpp and java hardly have much difference. Learn to understand logic, codes can follow. Else you will be struggling in your job with so much of spoon feeding. The code is there, just read it mate. And understand the cpp explanation. It runs parallely
Exactly 💯
I am also a java person but its understandable.
@@rajstriver5875 then please explain me why collectons.sort and comparable class both are used for ArrayList edges........if you know then please
@@Shivanai_h why comparator is used in class Edge and later why we used collections.sort.....I am confused
@@rajstriver5875 bhai fir edge class smjha
ye vector adj[] kya cheez hai ?
vector adj[] toh adj. list hoti hai pta hai 🤔🤔
2d vector hai jaise single vector mai sirf tum (node) store krte ho and double vector mai (node,weight)
vectoradj[ ] == vectoradj . Similarly, vector adj[] == vectoradj.
@@nownow1025 so, vector adj[] is just like a 3d array ?
@@anshumaan1024 I think chatgpt can tell in much detail.
nice
21jan 2024 7:10
understood :-)
striver supermacy
Why can't we use just the parent array to find out the ultimate parents of u and v?
That's what we are doing in findParent(). Whenever we insert a node to a set of nodes, the parent of the inserted node will change. So everytime we needa use findParent() func
Koi indore se hai kya bhai
code for someone who does not find declaring class , intuitive in exams
int findpar(int &a,vector &parent)
{
if(a==parent[a])
{
return a;
}
return parent[a] = findpar(parent[a],parent);
}
int spanningTree(int V, vector adj[])
{
vector parent(V);
for(int i=0;i
🐐
US
Here is java code of gfg practise link
class Solution {
static class DisjointSet {
List rank = new ArrayList();
List parent = new ArrayList();
public DisjointSet(int n) {
for (int i = 0; i
Thanks:)
thnxx
bhai yr ye comparator or comparable smjh ni aara hain koi video bata de yr kaha se smjhu usko pliz
🎉
"Understood"
❤
java kruskal algorithm, creating edges list from adjacency list
class Solution{
static class DisJointSetSize { // UNION BY SIZE; MORE INTUITIVE; KRUSKAL ALGORITHM SUBMITTED AND TESTED for gfg
List parent = new ArrayList();
List size = new ArrayList();
public DisJointSetSize(int n) {
for (int i = 0; i a[2] - b[2]);
DisJointSetSize dsu = new DisJointSetSize(V);
int sum = 0;
for (int[] edge : edges) {
int u = edge[0];
int v = edge[1];
int weight = edge[2];
if (dsu.findUltimateParent(u) != dsu.findUltimateParent(v)) {
dsu.unionBySize(u, v);
sum += weight;
}
}
return sum;
}
}
bhai yr ye lambda expression smjh hi ni aari h kaha se clear kru ise bata do yr