G-47. Kruskal's Algorithm - Minimum Spanning Tree - C++ and Java

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
---------------------------------------------------------------------------------------------------------------------------

[@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

[@Mohini-rt4wu]

I am not getting what the M and N stands for, when you are calculating time complexities.

[@KiranKumar-sb3ti]

understood

[@coding8000]

you will be remembered in all three tenses i.e past, current, future., keep going bro, my power to you.

[@SumitKeshariMCS]

Understood each and every second of the video. Thanks Striver.

[@raghavagrawal9240]

Was waiting for the series to continue! Thanks

[@cinime]

Understood! Super wonderful explanation as always, thank you!!

[@averylazyandweirdhuman]

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

[@oqant0424]

Understood! Super wonderful explanation❤

[@rishabhgupta9846]

understood,great explanation

[@sahillakhani1962]

well explained sir. Understood clearly!

[@suryasingh2563]

Fully understood bhaiya...

[@prasannasippa5962]

understood striver.... Thank you so much

[@stith_pragya]

Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@mohammadahsan7873]

Superb Explanations... ❤👏

[@udaytewary3809]

Understood bhaiya 🙏❤️

[@amantripathi4100]

Bhai indeed the best teacher

[@ajaybabupatel1665]

understood, thanks raj

[@kshitijmishra2716]

when you said drivers code muje kuch yaad aaa gaya 😂😂🔥🔥 but yeah you are rider the dsa driver the one and only strive 😎😎

[@aakashgoswami2356]

bhai kehna kya chhata hai ?

[@vishnubanjara5209]

@@aakashgoswami2356 controversy ki baat kr rha h bhai vo but striver is best teacher for dsa learning

[@studybits1604]

@@vishnubanjara5209 i still didnt get it

[@abhishekkuntare4640]

Understood Raj bhaiyaa ❤❤

[@suryasingh2563]

Understood Bhaiya❣

[@parshchoradia9909]

Understood Sir!

[@UECAshutoshKumar]

Thank you sir 🙏

[@user-fs8km9qc8f]

very nice explanation

[@anshulagarwal6682]

Please also make video on dp on trees, heavy light decomposition.

[@UjjwalPratapSingh-hh6wu]

Understood 👍🏻

[@SatyamKumar-bw4vi]

Great Video as Always..!

[@mugambo5505]

understood thanks sir ❣❣❣❣

[@Shivanai_h]

Understood 👏

[@herculean6748]

Thanks🙌

[@riteshkumargupta4001]

understood bhaiya

[@rohitn6333]

understood sir

[@officialashish5224]

understood!

[@dharanyuvi6951]

Understood Striver thanks

[@tatipamularaviteja5245]

understood❤

[@suryakiran2970]

Understood❤

[@priyan8004]

Understood !

[@AryanMathur-gh6df]

UNDERSTOOD

[@AmanGupta-ib5ss]

understood :)

[@amanxsharma]

understood

[@sanchitdeepsingh9663]

thanks sir

[@dreamyme543]

Understood:)

[@shivanshpatel7352]

Mast hai bhai

[@ujalavarshney480]

Understood

[@kandariarjun]

Understood!!

[@The_Shubham_Soni]

Understood.

[@phen8318]

Can we use priority queue here, instead of sorting the vector?

[@chiragbirla5606]

The logic kind of is if you join the edge with the same ultimate parent it would cause a cycle which is not allowed

[@priyanshkumariitd]

Yeah!!

[@durgeshjadhav01]

nice

[@ce003abhimanyu9]

why not added both direction edges?

[@_Deepak__Verma]

how do you calculated time complexity it's typical to understand

[@shreyarawatvlogs6920]

cant we directly sort adj list??? Why do we have to make vector edges?

[@Purvilicious]

why do we need bidirectional AL in here? unidirectional also gives same results

[@codewithasma8494]

On GFG this approach is giving TLE can someone help me to understand

[@ashrafmohammad2784]

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🙏🙏

[@saurabhsagar3134]

Edges print krna hai jo ki part hai mst ka

[@shivanshchakrawarti5582]

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

[@nilakshirekhawar2861]

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 ?

[@roshangeorge97]

btw this video is not yet updated with Striver SDE Sheet, had to search up this manually!!

[@technogaurav7980]

why is the *2 used in time complexity

[@prasadjambhale6670]

So which method is efficient for finding mst krushkal's or prim's

[@lucygaming9726]

Both appears to have same TC

[@softwarefoodiee]

We can use min heap instead of sorting the vector.

[@jagannathanav5108]

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

[@champion5946]

[@sumanthreddy7670]

why will the disjoint set ignore the undirected edges in the adjacency list? why will only one edge be considered in disjoint set?

[@harshith4549]

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"

[@ayushvarun1425]

what is aplha???i have forgotten about it.....can anyone explain it??

[@anshumaan1024]

its value is nearly 1

[@codingalley6229]

🐐

[@shivamchoudhury9791]

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.

[@debangshudey5515]

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 .

[@devans1244]

why are we not using visited array concept where if both vertex are visited we ignore the edge as it is making a loop

[@saillaanil6948]

good idea, have you tried solving using this way

[@harshathammegowda1615]

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.

[@googleit2490]

Understood :) Sep'5, 2023 12:03 am Advice to self: I guess I will need to revise again after week and month; seems Tricky

[@codecrafts5263]

but in code we were connecting ultimate parent of u with v, why are we connecting with u and v?

[@arnabroy2995]

❤

[@DeepakSingh-lr1og]

Can anyone tell me why 2 is connected to 1, it should be connected to 4, according to the disjoint set?

[@harshith4549]

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.

[@pratyakshhhhhhhhhhhhhhhhhhhhh]

🎉

[@Yourclassmate]

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

[@The_Shubham_Soni]

We have to write this whole DisjointSet class everytime for this type of questions?💀💀

[@shreedevimg]

when he said for java people i am like😎

[@anshumaan1024]

ye vector adj[] kya cheez hai ? vector adj[] toh adj. list hoti hai pta hai 🤔🤔

[@lofireverbz-wy7go]

2d vector hai jaise single vector mai sirf tum (node) store krte ho and double vector mai (node,weight)

[@techinfolbf1225]

No one can match striver energy and research for every video .........

[@prisha1765]

class Disjointset { vectorrank,parent; public: Disjointset(int n) { rank.resize(n+1,0); parent.resize(n+1); for(int i=1;i

[@vivekpawar311]

US

[@AbhijeetSingh-rx9ef]

Why can't we use just the parent array to find out the ultimate parents of u and v?

[@phoenix_1_3]

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

[@ProudSanataniHindu1008]

Can you please explain Java code also along with C++

[@rajstriver5875]

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

[@Shivanai_h]

Exactly 💯 I am also a java person but its understandable.

[@amanagrawal1951]

@@rajstriver5875 then please explain me why collectons.sort and comparable class both are used for ArrayList edges........if you know then please

[@amanagrawal1951]

@@Shivanai_h why comparator is used in class Edge and later why we used collections.sort.....I am confused

[@prathambhushan4859]

@@rajstriver5875 bhai fir edge class smjha

[@snipper6683]

Koi indore se hai kya bhai

[@kushagramishra3026]

"Understood"

[@atharm.7319]

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 ```

[@AshmitIITH]

Thanks bro

[@usnikdaripa]

babbar bhaiya ne graph k naam pe kaat diya hain

[@Mohit_Q]

21jan 2024 7:10

[@ankitraj2283]

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

[@roshangeorge97]

Thanks:)

[@modiji8706]

thnxx

[@thaman701]

bhai yr ye comparator or comparable smjh ni aara hain koi video bata de yr kaha se smjhu usko pliz

[@prathambhushan4859]

any java peeps, pls help me I am stuck at the code

[@devsrivastava2300]

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

[@KratosProton]

a

[@prathambhushan4859]

Have to write disjoint code💀💀

[@studybits1604]

us

[@AkashKumar-eo8ku]

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; } }

[@thaman701]

bhai yr ye lambda expression smjh hi ni aari h kaha se clear kru ise bata do yr

[@KratosProton]

t

[@KratosProton]

e

[@p38_amankuldeep75]

understood💙🤍💙

[@nkvs1248]

U.S.

[@river.]

i am python people. please help us python people too

[@shubhamkumar-hx1fb]

then..Do u want him to teach python?

[@river.]

@@shubhamkumar-hx1fb actually no. I am now a consultant analyst people. Fate guides my destination 🤘

[@rahulnagwanshi2348]

2:41 "Everyone will be a single guy" so basically he meant "Sabka Katega🔪"

[@kartikdalai7998]

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; } }

[@itsaryanb9316]

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?

[@stephen9726]

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.

[@shaikabdulsalambatcha4322]

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; } }

[@-VLaharika]

Understood 👍