Kruskal Algorithm

CS62, December, 2001
Question 4(b): Write Kruskal's Algorithm.

Answer: Kruskal's Algorithm enables us to find a minimal spanning tree T of a connected weighted graph G where n vertices. (In which case T must have n-1 edge.

Steps of Kruskal's Algorithm: The input is a connected weighted graph G wigh n vertices.

Step 1: Arrange the edges of G in order of increasing weights.
Step 2: Starting only with vertices of G and processing sequentially, add each edge which does not result in a cycle until n-1 edges are added.
Step 3: Exit

The algorithm is easily executed when graph G is small.