 |  |  |
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.
Click to see a PSEUDOCODE for the KRUSKAL algorithm.
| | |
HTML PAGE DIRECTOR :Papaioannou Panagiotis