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

Поділитися
Вставка
  • Опубліковано 22 гру 2024

КОМЕНТАРІ • 221

  • @takeUforward
    @takeUforward  2 роки тому +53

    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
      @Mohini-rt4wu 8 місяців тому

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

    • @KiranKumar-sb3ti
      @KiranKumar-sb3ti 5 місяців тому

      understood

  • @mrmttr3
    @mrmttr3 4 місяці тому +101

    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.

    • @SatyamKumar-eb3gi
      @SatyamKumar-eb3gi 3 місяці тому +5

      Thanks for this and it's very useful

    • @chetanraghavv
      @chetanraghavv 2 місяці тому +2

      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

    • @nownow1025
      @nownow1025 2 дні тому

      @@chetanraghavv Thanks

  • @coding8000
    @coding8000 Рік тому +90

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

  • @SumitKeshariMCS
    @SumitKeshariMCS 2 роки тому +16

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

  • @averylazyandweirdhuman
    @averylazyandweirdhuman 6 місяців тому +4

    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

  • @kshitijmishra2716
    @kshitijmishra2716 2 роки тому +53

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

    • @aakashgoswami2356
      @aakashgoswami2356 2 роки тому +9

      bhai kehna kya chhata hai ?

    • @vishnubanjara5209
      @vishnubanjara5209 Рік тому +9

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

    • @studybits1604
      @studybits1604 Рік тому

      @@vishnubanjara5209 i still didnt get it

  • @stith_pragya
    @stith_pragya Рік тому +2

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

  • @yashshukla1637
    @yashshukla1637 2 дні тому

    AWESOME! Loved it how he build concept from Disjoint sets.

  • @cinime
    @cinime 2 роки тому +3

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

  • @raghavagrawal9240
    @raghavagrawal9240 2 роки тому +1

    Was waiting for the series to continue! Thanks

  • @amantripathi4100
    @amantripathi4100 Рік тому +1

    Bhai indeed the best teacher

  • @udaytewary3809
    @udaytewary3809 Рік тому +1

    Understood bhaiya 🙏❤️

  • @vaibhavs2740
    @vaibhavs2740 4 місяці тому +1

    I solved this by myself after learning DSU, can I say I'm also a co-inventor of Kruskal's algortihm.

  • @chiragbirla5606
    @chiragbirla5606 Рік тому +11

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

  • @oqant0424
    @oqant0424 2 роки тому +1

    Understood!
    Super wonderful explanation❤

  • @rishabhgupta9846
    @rishabhgupta9846 2 роки тому +2

    understood,great explanation

  • @codeling4877
    @codeling4877 2 місяці тому

    One goog thing about krushkal is even you have multiple components , it can form MST in all those components

  • @anshulagarwal6682
    @anshulagarwal6682 2 роки тому +3

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

  • @UECAshutoshKumar
    @UECAshutoshKumar Рік тому +1

    Thank you sir 🙏

  • @ajaybabupatel1665
    @ajaybabupatel1665 Рік тому +1

    understood, thanks raj

  • @ce003abhimanyu9
    @ce003abhimanyu9 9 місяців тому +2

    why not added both direction edges?

  • @mohammadahsan7873
    @mohammadahsan7873 Рік тому

    Superb Explanations... ❤👏

  • @4rocraagas3
    @4rocraagas3 Місяць тому +1

    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?

  • @phen8318
    @phen8318 6 місяців тому +1

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

  • @nilakshirekhawar2861
    @nilakshirekhawar2861 5 місяців тому

    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 ?

  • @suryasingh2563
    @suryasingh2563 Рік тому

    Fully understood bhaiya...

  • @_Deepak__Verma
    @_Deepak__Verma 9 місяців тому +1

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

  • @VarshaSingh-hi2sb
    @VarshaSingh-hi2sb 4 місяці тому +1

    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

    • @6mahine_mein_google
      @6mahine_mein_google 4 місяці тому +1

      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

    • @VarshaSingh-hi2sb
      @VarshaSingh-hi2sb 4 місяці тому

      @@6mahine_mein_google so how its time complexity is N+E

  • @sahillakhani1962
    @sahillakhani1962 Рік тому

    well explained sir. Understood clearly!

  • @suryasingh2563
    @suryasingh2563 Рік тому

    Understood Bhaiya❣

  • @pallavigkumaraswamy5874
    @pallavigkumaraswamy5874 4 місяці тому

    Understood clearly!!!!

  • @abhishekkuntare4640
    @abhishekkuntare4640 2 роки тому

    Understood Raj bhaiyaa ❤❤

  • @chandanc7545
    @chandanc7545 2 дні тому

    we could have used same edges array in solution to add to List right, why was the adjacency list created

  • @nownow1025
    @nownow1025 День тому

    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)

  • @sumanthreddy7670
    @sumanthreddy7670 6 місяців тому +1

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

    • @harshith4549
      @harshith4549 5 місяців тому +1

      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"

  • @itsaryanb9316
    @itsaryanb9316 2 роки тому +5

    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
      @stephen9726 2 роки тому +3

      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.

  • @prasannasippa5962
    @prasannasippa5962 Рік тому

    understood striver.... Thank you so much

  • @googleit2490
    @googleit2490 Рік тому +1

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

  • @shreyarawatvlogs6920
    @shreyarawatvlogs6920 11 місяців тому

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

  • @ashrafmohammad2784
    @ashrafmohammad2784 Рік тому +5

    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
      @saurabhsagar3134 Рік тому

      Edges print krna hai jo ki part hai mst ka

    • @shivanshchakrawarti5582
      @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

  • @VrundLeuva-g5s
    @VrundLeuva-g5s 5 місяців тому

    very nice explanation

  • @dharanyuvi6951
    @dharanyuvi6951 5 місяців тому

    Understood Striver thanks

  • @Purvilicious
    @Purvilicious Рік тому

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

  • @UjjwalPratapSingh-hh6wu
    @UjjwalPratapSingh-hh6wu Рік тому

    Understood 👍🏻

  • @SatyamKumar-bw4vi
    @SatyamKumar-bw4vi Рік тому

    Great Video as Always..!

  • @parshchoradia9909
    @parshchoradia9909 Рік тому

    Understood Sir!

  • @ayushvarun1425
    @ayushvarun1425 Рік тому +3

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

  • @devans1244
    @devans1244 Рік тому +2

    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
      @saillaanil6948 Рік тому

      good idea, have you tried solving using this way

    • @harshathammegowda1615
      @harshathammegowda1615 Рік тому +3

      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.

  • @suryakiran2970
    @suryakiran2970 Рік тому

    Understood❤

  • @herculean6748
    @herculean6748 Рік тому

    Thanks🙌

  • @AryanMathur-gh6df
    @AryanMathur-gh6df Рік тому

    UNDERSTOOD

  • @ujalavarshney480
    @ujalavarshney480 2 роки тому +1

    Understood

  • @tatipamularaviteja5245
    @tatipamularaviteja5245 Рік тому

    understood❤

  • @technogaurav7980
    @technogaurav7980 6 місяців тому

    why is the *2 used in time complexity

  • @rohitn6333
    @rohitn6333 Рік тому +1

    understood sir

  • @shivamchoudhury9791
    @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
      @debangshudey5515 8 місяців тому

      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 .

  • @Shivanai_h
    @Shivanai_h 2 роки тому

    Understood 👏

  • @prasadjambhale6670
    @prasadjambhale6670 2 роки тому +2

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

  • @priyan8004
    @priyan8004 Рік тому

    Understood !

  • @mugambo5505
    @mugambo5505 2 роки тому

    understood thanks sir ❣❣❣❣

  • @prashanjeetkumar1999
    @prashanjeetkumar1999 4 місяці тому

    understood!!!

  • @softwarefoodiee
    @softwarefoodiee Рік тому

    We can use min heap instead of sorting the vector.

    • @jagannathanav5108
      @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

  • @riteshkumargupta4001
    @riteshkumargupta4001 2 роки тому

    understood bhaiya

  • @viholvishwassinh1709
    @viholvishwassinh1709 2 місяці тому +1

    solved by my self

  • @jinhuang7258
    @jinhuang7258 Рік тому

    Understood.

  • @roshangeorge97
    @roshangeorge97 Рік тому

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

  • @officialashish5224
    @officialashish5224 Рік тому

    understood!

  • @champion5946
    @champion5946 Рік тому

  • @prisha1765
    @prisha1765 Рік тому +4

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

  • @DeepakSingh-lr1og
    @DeepakSingh-lr1og 8 місяців тому

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

    • @harshith4549
      @harshith4549 5 місяців тому

      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.

  • @codecrafts5263
    @codecrafts5263 10 місяців тому

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

  • @Yourclassmate
    @Yourclassmate Рік тому +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

  • @dreamyme543
    @dreamyme543 Рік тому

    Understood:)

  • @sanchitdeepsingh9663
    @sanchitdeepsingh9663 5 місяців тому

    thanks sir

  • @codewithasma8494
    @codewithasma8494 Рік тому

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

  • @Rajat_maurya
    @Rajat_maurya 2 роки тому

    understood

  • @shivanshpatel7352
    @shivanshpatel7352 2 роки тому

    Mast hai bhai

  • @AmanGupta-ib5ss
    @AmanGupta-ib5ss 2 роки тому

    understood :)

  • @The_Shubham_Soni
    @The_Shubham_Soni Рік тому

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

  • @shreedevimg
    @shreedevimg 5 місяців тому

    when he said for java people i am like😎

  • @ProudSanataniHindu1008
    @ProudSanataniHindu1008 2 роки тому

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

    • @rajstriver5875
      @rajstriver5875 2 роки тому +10

      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
      @Shivanai_h 2 роки тому +4

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

    • @amanagrawal1951
      @amanagrawal1951 Рік тому +2

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

    • @amanagrawal1951
      @amanagrawal1951 Рік тому

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

    • @prathambhushan4859
      @prathambhushan4859 6 місяців тому

      @@rajstriver5875 bhai fir edge class smjha

  • @anshumaan1024
    @anshumaan1024 Рік тому

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

    • @lofireverbz-wy7go
      @lofireverbz-wy7go Рік тому

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

    • @nownow1025
      @nownow1025 2 дні тому

      vectoradj[ ] == vectoradj . Similarly, vector adj[] == vectoradj.

    • @anshumaan1024
      @anshumaan1024 День тому

      @@nownow1025 so, vector adj[] is just like a 3d array ?

  • @prathambhushan4859
    @prathambhushan4859 6 місяців тому +7

    Have to write disjoint code💀💀

  • @atharm.7319
    @atharm.7319 2 роки тому +8

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

  • @durgeshjadhav01
    @durgeshjadhav01 5 місяців тому

    nice

  • @addityasharma6426
    @addityasharma6426 2 роки тому

    understood :-)

  • @usnikdaripa
    @usnikdaripa Рік тому

    babbar bhaiya ne graph k naam pe kaat diya hain

  • @Mohit_Q
    @Mohit_Q 11 місяців тому

    21jan 2024 7:10

  • @bite-sized-storie5
    @bite-sized-storie5 2 роки тому +1

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

  • @AbhijeetSingh-rx9ef
    @AbhijeetSingh-rx9ef Рік тому

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

    • @phoenix_1_3
      @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

  • @ShubhamKumar-k6q
    @ShubhamKumar-k6q 4 місяці тому

    striver supermacy

  • @devsrivastava2300
    @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

  • @pratyakshhhhhhhhhhhhhhhhhhhhh

    🎉

  • @snipper6683
    @snipper6683 7 місяців тому

    Koi indore se hai kya bhai

  • @arnabroy2995
    @arnabroy2995 Рік тому

  • @vivekpawar311
    @vivekpawar311 Рік тому

    US

  • @ankitraj2283
    @ankitraj2283 Рік тому +4

    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
      @roshangeorge97 Рік тому +1

      Thanks:)

    • @modiji8706
      @modiji8706 Рік тому

      thnxx

    • @thaman701
      @thaman701 5 місяців тому +3

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

  • @AkashKumar-eo8ku
    @AkashKumar-eo8ku 7 місяців тому

    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
      @thaman701 5 місяців тому

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

  • @codingalley6229
    @codingalley6229 Рік тому

    🐐

  • @kushagramishra3026
    @kushagramishra3026 2 роки тому

    "Understood"