Kruskal’s MST
Let’s start with defining what we are searching for – the Minimum Spanning Tree.
MST is a tree built on vertices of a given graph, so the total weight of all edges is minimum among all possible vertices. This graph is a subgraph of the given, and it contains V-1 edges, where V is a number of vertices.
One of the approaches to build MST is using Kruskal’s MST Algorithm:
-
Sort all edges by weight in ascending order
-
Label each vertex by the number of subtree it belongs to. In the beginning, each vertex is a separate single-element subtree. 3) Pick the first edge. Edge's vertices belong to different subtrees, so you can join them into one subtree. To do that, make their labels the same.
-
Pick the next 'smallest' edge. Check if the edge's vertices belong to different subtrees. If yes, change labels to join all vertices into one.
-
Repeat 3 until all vertices belong to one subtree. This tree is the answer.
Swipe to start coding
Follow the comments in code to complete the algorithm.
Solution
Thanks for your feedback!
single
Ask AI
Ask AI
Ask anything or try one of the suggested questions to begin our chat
Summarize this chapter
Explain the code in file
Explain why file doesn't solve the task
Awesome!
Completion rate improved to 7.69Kruskal’s MST
Swipe to show menu
Let’s start with defining what we are searching for – the Minimum Spanning Tree.
MST is a tree built on vertices of a given graph, so the total weight of all edges is minimum among all possible vertices. This graph is a subgraph of the given, and it contains V-1 edges, where V is a number of vertices.
One of the approaches to build MST is using Kruskal’s MST Algorithm:
-
Sort all edges by weight in ascending order
-
Label each vertex by the number of subtree it belongs to. In the beginning, each vertex is a separate single-element subtree. 3) Pick the first edge. Edge's vertices belong to different subtrees, so you can join them into one subtree. To do that, make their labels the same.
-
Pick the next 'smallest' edge. Check if the edge's vertices belong to different subtrees. If yes, change labels to join all vertices into one.
-
Repeat 3 until all vertices belong to one subtree. This tree is the answer.
Swipe to start coding
Follow the comments in code to complete the algorithm.
Solution
Switch to desktop for real-world practiceContinue from where you are using one of the options belowThanks for your feedback!
Awesome!
Completion rate improved to 7.69single
