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

In case you are thinking to buy courses, please check below:

---------------------------------------------------------------------------------------------------------------------------

[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

[mrmttr]

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.

[coding]

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.

[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

[kshitijmishra]

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

[raghavagrawal]

Was waiting for the series to continue! Thanks

[cinime]

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

[chiragbirla]

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

[oqant]

Understood!
Super wonderful explanation❤

[anshulagarwal]

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

[sahillakhani]

well explained sir. Understood clearly!

[prasannasippa]

understood striver.... Thank you so much

[_Deepak__Verma]

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

[phen]

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

[nilakshirekhawar]

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 ?

[itsaryanb]

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?

[VarshaSingh-hisb]

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

[vaibhavs]

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