G-47. Kruskal's Algorithm - Minimum Spanning Tree - C++ and Java
Вставка
- Опубліковано 21 жов 2022
- GfG-Problem Link: bit.ly/3eLuYvH
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,.
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
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.
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
Was waiting for the series to continue! Thanks
Understood! Super wonderful explanation as always, thank you!!
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
Understood!
Super wonderful explanation❤
well explained sir. Understood clearly!
understood,great explanation
Superb Explanations... ❤👏
Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
understood striver.... Thank you so much
Fully understood bhaiya...
Bhai indeed the best teacher
Understood bhaiya 🙏❤️
Please also make video on dp on trees, heavy light decomposition.
Understood Raj bhaiyaa ❤❤
understood, thanks raj
Understood Bhaiya❣
very nice explanation
Understood Sir!
Thank you sir 🙏
Can we use priority queue here, instead of sorting the vector?
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!!
Understood 👍🏻
understood thanks sir ❣❣❣❣
understood bhaiya
Understood 👏
understood sir
cant we directly sort adj list??? Why do we have to make vector edges?
Thanks🙌
Great Video as Always..!
understood!
how do you calculated time complexity it's typical to understand
Understood❤
Understood!!
understood❤
Understood !
UNDERSTOOD
why not added both direction edges?
why do we need bidirectional AL in here? unidirectional also gives same results
understood
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.
btw this video is not yet updated with Striver SDE Sheet, had to search up this manually!!
Understood
Understood:)
understood :)
Mast hai bhai
So which method is efficient for finding mst krushkal's or prim's
Both appears to have same TC
Understood.
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
On GFG this approach is giving TLE can someone help me to understand
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 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
nice
why is the *2 used in time complexity
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"
but in code we were connecting ultimate parent of u with v, why are we connecting with u and v?
class Disjointset
{
vectorrank,parent;
public:
Disjointset(int n)
{
rank.resize(n+1,0);
parent.resize(n+1);
for(int i=1;i
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 :)
Sep'5, 2023 12:03 am
Advice to self: I guess I will need to revise again after week and month; seems Tricky
what is aplha???i have forgotten about it.....can anyone explain it??
its value is nearly 1
🐐
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.
❤
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
🎉
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)
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
We have to write this whole DisjointSet class everytime for this type of questions?💀💀
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
No one can match striver energy and research for every video .........
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
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
Koi indore se hai kya bhai
any java peeps, pls help me I am stuck at the code
"Understood"
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
babbar bhaiya ne graph k naam pe kaat diya hain
a
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;
}
}
21jan 2024 7:10
us
e
t
understood💙🤍💙
Have to write disjoint code💀💀
i am python people. please help us python people too
then..Do u want him to teach python?
@@shubhamkumar-hx1fb actually no. I am now a consultant analyst people. Fate guides my destination 🤘
U.S.
2:41 "Everyone will be a single guy" so basically he meant "Sabka Katega🔪"
public class KrushkalDriver {
public static void main(String[] args) {
findMSTCost(createWeightedGraph());
}
public static void findMSTCost(ArrayList[] graph){
ArrayList list = new ArrayList();
for (int i = 0; i < graph.length; i++) {
for (int j = 0; j < graph[i].size(); j++) {
list.add(graph[i].get(j));
}
}
Collections.sort(list,(o1, o2) -> o1.weight- o2.weight);
DisjointSet d = new DisjointSet(graph.length);
int cost =0;
for (Edge e:list
) {
if(d.addBySize(e.src,e.dst)){
cost= cost+e.weight;
}
}
System.out.println(cost);
}
public static ArrayList[] createWeightedGraph(){
int V = 4;
ArrayList[] graph = new ArrayList[V];
for (int i = 0; i < V; i++) {
graph[i] = new ArrayList();
}
graph[0].add(new Edge(0,1,10));
graph[0].add(new Edge(0,2,15));
graph[0].add(new Edge(0,3,30));
graph[1].add(new Edge(1,0,10));
graph[1].add(new Edge(1,3,40));
graph[2].add(new Edge(2,0,15));
graph[2].add(new Edge(2,3,50));
graph[3].add(new Edge(3,1,40));
graph[3].add(new Edge(3,0,30));
graph[3].add(new Edge(3,2,50));
return graph;
}
}
class Edge{
int src;
int dst;
int weight;
public Edge(int src, int dst, int weight) {
this.src = src;
this.dst = dst;
this.weight = weight;
}
}
class DisjointSet{
ArrayList size = new ArrayList();
ArrayList parent = new ArrayList();
public DisjointSet(int n) {
for (int i = 0; i sizeV){
parent.set(ulPv,ulPu);
size.set(ulPu,sizeU+sizeV);
}else {
parent.set(ulPu,ulPv);
size.set(ulPv,sizeU+sizeV);
}
return true;
}
}
Optimal Java Code:
class DisjointSetUnion {
ArrayList parent=new ArrayList();
ArrayList rank=new ArrayList();
public DisjointSetUnion(int n){
for(int i=0;i rank.get(ulv)){
parent.set(ulv,ulu);
}
else{
parent.set(ulv,ulu);
int ranku=rank.get(ulu);
rank.set(ulu, ranku+1);
}
}
}
class Solution{
static int spanningTree(int V, int E, int edges[][]){
// Code Here.
Arrays.sort(edges,(x,y)->x[2]-y[2]);
DisjointSetUnion ds=new DisjointSetUnion(V);
int netwt=0;
for(int[] num: edges){
int wt=num[2];
int u=num[0];
int v=num[1];
if(ds.findpar(u) != ds.findpar(v)){
netwt+=wt;
ds.union(u,v);
}
}
return netwt;
}
}
Understood 👍
Understood!
understood
Understood.
Understood