Kruskal’s algorithm


In general, a sequence of instructions that solve all instances of a well-defined problem is called an algorithm. The algorithm used to find a minimum cost spanning tree in a graph is called greedy. We greedily choose the edges of the graph to build our tree hat are of least weight, as long as they do not create a circuit.

The Kruskal Algorithm starts with a forest which consists of n trees. Each and everyone tree,consists only by one node and nothing else. In every step of the algorithm, two different trees of this forest are connected to a bigger tree.

Therefore, we keep having less and bigger trees in our forest until we end up in a tree which is the minimum genetic tree (m.g.t.).

In every step we choose the side with the least cost, which means that we are still under greedy policy. If the chosen side connects nodes which belong in the same tree the side is rejected, and not examined again because it could produce a circle which will destroy our tree.

Either this side or the next one in order of least cost will connect nodes of different trees, and this we insert connecting two small trees into a bigger one.

  1.  

    Set i=1 and let E0={}

  2. Select an edge ei of minimum value not in Ei-1 such that Ti=<Ei-1 cup {ei} >is acyclic and define Ei=Ei-1 cup {ei}. If no such edge exists, Let T=<Ei>and stop.
  3. Replace i by i+1. Return to Step 2.

The time required by Kruskal’s algorithm is O(|E|log|V|).

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s