Kruskal’s Algorithm

Kruskal’s algorithm is used to find minimum spanning tree in a weighted undirected graph. A spanning tree of a undirected graph G is a sub-graph that includes all vertices of G and satisfies conditions of a tree. On the diagram below you can find two graphs and only left graph can be considered as spanning tree.

span_tree_1

Because, the right graph has a cycle and this fact violates condition which states that a tree cannot have a cycle. 

Properties of the spanning tree
  1. If connected graph has vertices, then any spanning tree of this graph will have N-1 edges.
  2. Adding at least one edge to the spanning tree will create a cycle.
  3. Removal of edge from the spanning tree produces two disjoint sets.
  4. If a graph is not connected, then it must be considered as a spanning forest.
  5. A single graph can have many spanning trees. Because, vertices can be connected in different ways.
Minimum spanning tree

Minimum spanning tree or MST includes all properties of the spanning tree. Such trees have minimum sum of all weights. A graph can have more than one MST.

Lets consider an arbitrary  graph below:

mst_e_1

Using this graph we can get at least two spanning trees and only one minimum spanning tree.

mst_e_2

The minimum cost is 10.

Minimum spanning tree applications

Minimum spanning trees were first  used in building electrical grids to minimize costs of wiring. For instance, we can assume that vertices are houses and edges are wire. In such case, the MST will help to find minimal cost of wire. Nowadays, it is widely used in bulding computer networks, transportation networks, telecomunication networks.

Algorithm of searching minimum spanning trees can be used in more complex problems such as finding Steiner trees or Christofides algorithm which searches solution to solve traveling salesman problem.

Another intresting application of Kruscal’s and Prim’s algorithms is that both algorithms can be used in generating high-quality mazes.

Implementation

The given below undirected weighted graph has four vertices and five edges. Our goal is to find minimum spanning tree using Kruskal’s algorithm.

ka_e_1

The algorithm traverses over all edges in the graph starting from the shortest to the longest. The shortest edge 0<->2 in the graph has weight/length of 2, so – this will be our first edge in MST.

ka_e_2

The second shortest edge in the graph is 0 <-> 1 and it has weight of  3. We can add this edge to our MST, since it is shortest and doesn’t violate any conditions of MST.

ka_e_3

Now we have edges 1<->2, 1<->3 and 2<->3. The shortest edge is 1<->2, but we can’t use it since we will get a cycle. Edge 1<->3 has weight five and this is what we need, because another edge has weight  8.

ka_e_4

Сongratulations, our goal is completed!

Basing on the example above we can distinguish steps of the Kruskal’s algorithm:

  1. Create list which will contain edges of the MST.
  2. Create disjoint sets containing all vertices as singletons.
  3. For each edge (u, v) sorted in ascending order by weight do steps from 3.1 to 3.x.x.
    1. If u and v are not in the same set go to step 3.1.1.
      1. Add (u, v) to R.
      2. Union u and v.
  4. End.

The algorithm has Ο(E log V) complexity.

My Java version of Kruskal’s algorithm you can find on GitHub: https://github.com/alexvolov/algorithms-and-data-structures/blob/master/src/main/java/com/alexvolov/ads/algorithms/graph/KruskalsAlgorithm.java.

2 thoughts on “Kruskal’s Algorithm

  1. In above pseudo-code, corrections to be made at lines
    3 -> For each edge (u, v) sorted in ascending order by weight do steps from 3.1 to 3.x.
    3.1 – > If u and v are not in the same set go to step 3.1.1.

Leave a Reply