Kruskal's Algorithm - The Greedy One :)

KRUSKAL’S ALGORITHM
Presented by : Abraham,Pavan

Motivation : We all have experience with several different types of networks viz. Telephone networks, networks of roads and computer networks. One might ask a question about these networks viz. “What is the cheapest (or the shortest) way to linkall the objects together ?” . In a another similar situation , suppose we have a group of islands that we wish to link with bridges so that it is possible to travel from one island to the other. And , as it normally happens our government works within a limited budget, spends absolute minimum amount on this project.

The engineers are able to produce a cost for a bridge linking each possible pair of island. The set of bridges which will enable one to travel from any island to any other at minimum capital cost to the government is the minimum spanning tree. In order for a computer to solve a problem like this efficiently, it must be given a precise system for doing so. Computers have no way of figuring out the system for themselves, but if given an precise algorithm like the minimum spanning tree they do very well. How they do it ? this can be very easily understood if we look at some definitions first. These are as mentioned :

GRAPHS
A graph is a set of vertices and edges which connect them . We can write :

G = (V, E)

Where, V is the set of vertices and the set of edges,

E = { ( v i , v j ) }

Where, v i and v j are in V.

SPANNING TREES
A spanning tree of a graph, G , is aset of | V | - 1 edges that connect all vertices of the graph.

MINIMUM SPANNING TREE
In general it is possible to construct a multiple spanning trees for a graph , G. If a cost, C ij, is associated with each edge, eij = (vi , vj ) , then the minimum spanning tree is the set of edges, Espan , forming a spanning tree, such that :

C = sum( cij | all eij in Espan)

is a minimum.

GREEDY ALGORITHMS :
There is a class of algorithms, the greedy algorithms these always make the choice that look the best at that moment. That is, it makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution. The problem of finding the minimum spanning tree is a good example of this class

There are basically two minimum spanning tree algorithms, the Kruskal’s Algorithm and Prim’s Algorithm. They each use a specific rule to determine a safe edge in a generic – MST.

KRUSKAL’S ALGORITHM

This algorithm creates a forest, It finds a safe edge to add to the growing forest by finding, of all the edges that connect any two trees in the forest, an edge (u, v) of least weight. Let C1 and C2 denote the two trees that are connected by (u , v). Since, (u, v) must be a light edge connecting C1 to some other tree by the Corollary 24.2( CLR) implies that (u,v) is a safe edge for C1. This Algorithm is a greedy algorithm as at each step it adds to the forest an edge of least possible weight.

MST-KRUSKAL (G,w)
1. A ? ?
2. for each vertex v ? V[G]
3.          do MAKE_SET(v)
4. sort the edges of E by nondecreasing weight w
5. for each edge (u,v) ? E, in order by nondecreasing weight
6.       do if FIND-SET(u) ? FIND-SET(v)
7.                then A ? A U { (u, v) }
8.                        UNION(u, v)
9. return A

 The total running time of the Kruskal’s Algorithm is O( E lg E ).

View Applet

STEPS TO VIEW :

1. Select the type of graph by moving the scroll bar from the "START" towards the "END".

2. Press the "START" buttons on the main menu, this will show the graph with the nodes

   alongwith the marked edges shown in white.Starting with a graph with a minimum of 3x3

   nodes and a maximum of 20 X 20 nodes.

3. If you want to view the algorithm "step-by-step" press the "STEP" button for every step.

4. If want to view the algorithm in a continous flow press the "COMPUTE" buttton.

5. To clear the graph, select a new graph from the "Scroll bar" and press "START", a new

   graph would be displayed follow steps 1,2,3,4 and so on.

Source Files

Click here for complete source (.java) files.