Kruskal's

Visualisation of Kruskal's algorithm using networkx library

INPUT

Input is taken from the file

input.txt

Sample input

  5
  0 2 7 -1 -1
  2 0 3 8 5
  7 3 0 1 -1
  -1 8 1 0 4
  -1 5 -1 4 0

First line contains the number of nodes,say n.(Nodes are numbered as 0,1,2,...(n-1) ) Followed by n*n weighted matrix. Disconnected edges are represented by negative weight.

Draw Graph

Graph is first drawn from the weighted matrix input from the user with weights shown. Edges are marked with black.

Kruskal's algorithm

Kruskal's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected garph.

The algorithm operates by adding the egdes one by one in the order of their increasing lengths, so as to form a tree. Egdes are rejected if it's addition to the tree, forms a cycle. This continues till we have V-1 egdes in the tree. (V stands for the number of vertices).

To understand this better, consider the above input.

The graph, initially.

After the first iteration:

The smallest edge is of length 1, connecting Node 2 and Node 3. Since it is the first edge, it is added directly to the tree.

After the second iteration:

Next smallest edge is of length 2, connecting Node 0 and Node 1. Since it's addition doesn't result in a cycle, it is added to the tree.

After the third iteration:

Next smallest edge is of length 3, connecting Node 1 and Node 2. Since it's addition doesn't result in a cycle, it is added to the tree.

After the fourth iteration:

Next smallest edge is of length 4, connecting Node 3 and Node 4. Since it's addition doesn't result in a cycle, it is added to the tree.

Now we have 4 edges, hence we stop the iteration. Final graph, with red edges denoting the minimum spanning tree.

Complexity

Time: O(V^2)
V - Number of vertices