Kruskal’s method of Spanning Tree and Comparing with Round Robin’s Algorithm.

Kruskal’s method of spanning Tree is one of the methods of creating minimum spanning tree. In this method nodes of the graph are initially considered as ‘ n’ distinct partial trees with one node each. Then two distinct partial trees are connected into a single partial tree by an edge of the graph. While connecting two distinct trees the arc of minimum weight should be used, for that arcs are placed in a priority queue on the basis of weight. Then the arc of lowest weight is examined to see if it connects two distinct trees. To determine if an arc (x, y) connects distinct trees, we can implement the trees with a father field in each node. Then we can traverse all ancestors of x and y to obtain the roots of the trees containing them. If the roots of the two trees are the same node, x and y are already in the same tree, so arc (x, y) is discarded, and the arc of next lowest weight is examined. Combining two trees simply involves setting the father of the root of one to the root of the other. This method requires O (e log e) operations
Round Robin’s algorithm is another method of spanning tree, which provides better performance when the number of edges is low. This algorithm is similar to Kruskal’s method except that there is a priority queue of arcs associated with each partial tree, rather than one global priority queue of all unexamined arcs. For this at first all partial trees are maintained in a queue,Q. Associated with each partial tree, T, is a priority queue ,P(T),of all arcs with exactly one incident node in the tree, ordered by the weights of the arcs. Then a priority queue of all arcs incident to ‘nd’ is created for each node ‘nd’, and the single–node trees are inserted into Q in arbitrary order. The algorithm proceeds by removing a partial tree,T1, from the front of Q; finding the minimum –weight arc a in P(T1);deleting from Q the tree ,T2,at the other end of arc a; combining T1 and T2 into a single new tree T3 [and at the same time combining P(T1) and P(T2),with a deleted ,into P(T3)];and adding T3 to the rear of Q. This continues until Q contains a single tree: the minimum spanning tree. This algorithm requires only O(e log n) operations if appropriate implementation of the priority queues is used .