Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Kruskal’s MST | Greedy on Graphs
Greedy Algorithms using Python
course content

Course Content

Greedy Algorithms using Python

Greedy Algorithms using Python

1. Greedy Algorithms: Overview and Examples
Why Greedy?Description and Simple ExampleSchedule ProblemEuclidean AlgorithmEgyptian Fraction ProblemJob Sequencing Problem
2. Greedy on Arrays
Make Arrays EqualMinimum Product SubsetJumping Frog
3. Greedy on Graphs
PreparationDijkstra Shortest Path AlgorithmKruskal’s MSTPrim's MST

bookKruskal’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:

  1. Sort all edges by weight in ascending order
  2. 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.
  3. 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.
  4. Repeat 3 until all vertices belong to one subtree. This tree is the answer.

Task

Follow the comments in code to complete the algorithm.

Switch to desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
Everything was clear?

How can we improve it?

Thanks for your feedback!

Section 3. Chapter 3
toggle bottom row

bookKruskal’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:

  1. Sort all edges by weight in ascending order
  2. 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.
  3. 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.
  4. Repeat 3 until all vertices belong to one subtree. This tree is the answer.

Task

Follow the comments in code to complete the algorithm.

Switch to desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
Everything was clear?

How can we improve it?

Thanks for your feedback!

Section 3. Chapter 3
toggle bottom row

bookKruskal’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:

  1. Sort all edges by weight in ascending order
  2. 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.
  3. 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.
  4. Repeat 3 until all vertices belong to one subtree. This tree is the answer.

Task

Follow the comments in code to complete the algorithm.

Switch to desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
Everything was clear?

How can we improve it?

Thanks for your feedback!

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:

  1. Sort all edges by weight in ascending order
  2. 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.
  3. 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.
  4. Repeat 3 until all vertices belong to one subtree. This tree is the answer.

Task

Follow the comments in code to complete the algorithm.

Switch to desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
Section 3. Chapter 3
Switch to desktopSwitch to desktop for real-world practiceContinue from where you are using one of the options below
some-alt