Create Minimum Spanning Tree | Kruskal's Algorithm Explained and Implemented in Java | Geekific

In one of our very first introductory graph videos we explained what spanning trees are. Basically, any graph can span multiple other graphs, but not just any graph, trees in particular. And that is what we call a spanning tree for this graph. In other terms, a spanning tree is a connected sub-graph that contains all the graph vertices with the minimum possible number of edges; which is the number or vertices in the graph minus one. In this video, we explain and implement Kruskal’s algorithm, which is one way among many that identifies this minimum spanning tree.

Timestamps:
00:00 Introduction
00:58 What is Kruskal's Algorithm?
03:03 Kruskal's Algorithm Implementation
06:25 Testing our Code
06:56 Thanks for Watching!

If you found this video helpful, check other Geekific uploads:

#Geekific #Kruskal #GraphTheory #SpanningTree #MinimumSpanningTree

[ruantristancarlinsky]

You are literally my favorite programming related channel! Your work is very concise and well explained. I hope your channel grows larger and larger so you get more recognition for your amazing work:-)

[gabriellaudenwa]

@Geekific, Thank you for the rich content. The explanations are mind blowing😊

[ianakotey]

Great video, as always. I'd recommend a video on Kadane's algorithm. I'd refer my students to it

[svalyavasvalyava]

thank you for the wonderful content, as usually!

[manOfPlanetEarth]

Freaking awesome, again:)
Totally thrilled with the algorithm implementation.

Btw, nice approach to firstly display the main frame of code and only then the details. I almost always make pause and try to figure out those details. It makes develop.

[IamJustin-tkwz]

I like how you simplify stuff.


I have a question.

In the reset tree method, you reset the vertices and then just set up the temporary spanning tree. However I don't see where you add this to the vertices.

I was thinking maybe I should be seeing somewhere the vertices variable is updated

Or am I missing something.

[smngsiewming]

Thanks, your videos helped a lot with these theory.

Also why did you do cycle detection using DFS than Union find.

Should union find O(logN) be faster than DFS O(V + E)

[ahmedmohamed-rncy]

Could you add an Arabic translation, please?

[manOfPlanetEarth]

Just an idea: why not make "hasCycle" static and make import static of embracing class ("CycleDetection") to turn
"if (!new
into neater
"if (!hasCycle(vertices))"
😊

[manOfPlanetEarth]

Will allow myself a few thoughts out loud.

1. Vertex class in github has "beingVisited" property - looks like an artifact as graphs under consideration are undirected, aren't they?

2. Any special reason why Set is used for neighbors in Vertex class instead of List?🤔 At a glance found no code that could generate duplicates in neighbors collection.

3. Any special reason to use "do...while" in method "run" instead of "while loop"? See none, so it's a personal preference, isn't it?

4. Have small doubts about disconnected graph case. Consider a graph consisting of 2 not connected edges. "hasCycle" will return "false", both edges will be added to "spanningTree" collection. Right, sir?🤔 But it won't be a tree. Looks like a connectedness check for resulting "spanningTree" is required to handle such cases, doesn't it? To be more precise such check is required already for input graph: if input graph has more than 1 connected component there can be no question of a spanning tree. Your thoughts?