O'Reilly logo

C# Data Structures and Algorithms by Marcin Jamro

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Kruskal's algorithm

One of the algorithms for finding the MST was discovered by Kruskal. Its operation is very simple to explain. The algorithm takes an edge with the minimum weight from the remaining ones and adds it to the MST, only if adding it does not create a cycle. The algorithm stops when all nodes are connected.

Let's take a look at the diagram that presents the steps of finding the MST using Kruskal's algorithm:

In the first step, the edge (5, 8) is chosen, because it has the minimum weight, namely 1. Then, the edges (1, 2), (2, 4), (5, 6), (1, 3), (5, 7), and (4, 8) are selected. It is worth noting that before taking the (4, 8

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required