explain the Kruskal's algorithm with an example? or -> prove that Kruskal's algorithm finds a minimal spanning tree?

Kruskal's Algorithm

Kruskal's Algorithm for computing the minimum spanning tree is directly based on the generic MST algorithm. It builds the MST in forest. Initially, each vertex is in its own tree in forest. Then, algorithm consider each edge in turn, order by increasing weight. If an edge (u, v) connects two different trees, then (u, v) is added to the set of edges of the MST, and two trees connected by an edge (u, v) are merged into a single tree on the other hand, if an edge (u, v) connects two vertices in the same tree, then edge (u, v) is discarded.

Outline of Kruskal's Algorithm

Start with an empty set A, and select at every stage the shortest edge that has not been chosen or rejected, regardless of where this edge is situated in graph.

I    Kruskal's algorithm implemented with disjoint-sets data structure.

Disjoint-Sets Data Structure

• Make_Set (v)
  Create a new set whose only member is pointed to by v. Note that for this operation v must already be in a set.
• FIND_Set
  Returns a pointer to the set containing v.
• UNION (u, v)
  Unites the dynamic sets that contain u and v into a new set that is union of these two sets.

MST_KRUSKAL (G, w)

1.      A ← {}    // A will ultimately contains the edges of the MST

2.      for each vertex v in V[G]

3.          do Make_Set (v)

4.      Sort edge of E by nondecreasing weights w

5.      for each edge (u, v) in E

6.          do if FIND_SET (u) ≠ FIND_SET (v)

7.              then A = AU{(u, v)}

8.                  UNION (u, v)

9.      Return A

Analysis

The for-loop in lines 5-8 per forms 'Union' and 'find' operations in O(|E|) time. When the disjoint-set forest implementation with the weighted union and path compression heuristic is used, the O(|E|) 'union' and 'find' operators involved in the for-loop in lines 5-8 will have worst-case time O(|E| lg * |E|). Kruskal's algorithm requires sorting the edge of E in line 4. We know that the fastest comparison-based sorting algorithm will need (|E| lg |E|) time to sort all the edges. The time for sorting all the edges of G in line 4 will dominates the time for the 'union' and 'find' operations in the for-loop in lines 5-8. When comparison-based sorting algorithm is used to perform sorting in line 4. In this case, the running time of Kruskal's algorithm will be O(|E| lg |E|).

In summary, Kruskal's algorithm as given in the CLR, pp 505 requires O(E lg E) time

• O(V) time to initialize.
• O(E lg E) time to sort edges by weight
• O(E α (E, V)) = O(E lg E) time to process edges.

If all edge weights are integers ranging from 1 to |V|, we can use COUNTING_SORT (instead of a more generally applicable sorting algorithm) to sort the edges in O(V + E) = O(E) time. Note that V = O(E) for connected graph. This speeds up the whole algorithm to take only O(E α (E, V)) time; the time to process the edges, not the time to sort them, is now the dominant term. Knowledge about the weights won't help speed up any other part of the sort in line 4 uses the weight values.

If the edges weights are integers ranging from 1 to constant W, we can again use COUNTING_SORT, which again runs in O(W + E) = O(E) time. Note taht O(W + E) = O(E) because W is a constant. Therefore, the asymptotic bound of the Kruskal's algorithm is also O(E α (E, V)).

II    Kruskal's algorithm implemented with priority queue data structure.

MST_KRUSKAL (G)

1.      for each vertex v in V[G] do

2.          define set S(v) ← {v}

3.      Initialize priority queue Q that contains all edges of G, using the weights as keys.

4.      A ← { }         // A will ultimately contains the edges of the MST

5.      While A has less than n-1 edges do

6.      Let set S(v) contains v and S(u) contain u

7.      IF S(v) != S(u) then     Add edge (u, v) to A     Merge S(v) and S(u) into     one set i.e., union

8.      Return A

Analysis

• The edge weight can be compared in constant time.
• Initialization of priority queue takes O(E log E) time by repeated insertion.
• At each iteration of while-loop, minimum edge can be removed in O(log E) time, which is O(log V), since graph is simple.
• The total running time is O((V + E) log V), which is O(E lg V) since graph is simple and connected.

Example    Step by Step operation of Kurskal's algorithm.

Step 1.  In the graph, the Edge(g, h) is shortest. Either vertex g or vertex h could be representative. Lets choose vertex g arbitrarily.

Step 2. The edge (c, i) creates the second tree. Choose vertex c as representative for second tree.

Step 3. Edge (g, g) is the next shortest edge. Add this edge and choose vertex g as representative.

Step 4. Edge (a, b) creates a third tree.

Step 5. Add edge (c, f) and merge two trees. Vertex c is chosen as the representative.

Step 6. Edge (g, i) is the next next cheapest, but if we add this edge a cycle would be created. Vertex c is the representative of both.

Step 7. Instead, add edge (c, d).

Step 8. If we add edge (h, i), edge(h, i) would make a cycle.

Step 9. Instead of adding edge (h, i) add edge (a, h).

Step 10. Again, if we add edge (b, c), it would create a cycle. Add edge (d, e) instead to complete the spanning tree. In this spanning tree all trees joined and vertex c is a sole representative.