__Kruskal’s Algorithm__

__Kruskal’s Algorithm__

__-to find minimum spanning tree__

__-to find minimum spanning tree__

**A****l****g****o****rithm:**

**A****L****G****ORITHM Kruskal (G)**

//Kruskal’s algorithm for constructing a MST

//Input: A weighted connected graph G = { V, E }

//Output: ET the set of edges composing a MST of G

Sort E in ascending order of the edge weights

// initialize the set of tree edges and its size

### The method:

**STE****P 1**: Sort the edges by increasing weight

**STE****P 2**: Start with a forest having |V| number of trees.

**STE****P 3**: Number of trees are reduced by ONE at every inclusion of an edge At each stage:

• Among the edges which are not yet included, select the one with minimum weight AND which does not form a cycle.

• the edge will reduce the number of trees by one by combining two trees of the forest

#### Algorithm stops when |V| -1 edges are included in the MST i.e : when the number of trees in the forest is reduced to ONE.

**Example:**

Apply Kruskal’s algorithm for the following graph to find MST.

Efficiency:

Efficiency of Kruskal’s algorithm is based on the time needed for sorting the edge weights of a given graph.

• With an efficient sorting algorithm:

Efficiency:Θ(|E| log |E| )

### Conclusion:

Kruskal’s algorithm is an “edge based algorithm” Prim’s algorithm with a heap is faster than Kruskal’s algorithm.