---

Kruskals Algorithm

---

• Kruskal's algorithm is a greedy algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.
• Kruskal’s algorithm is used to find the minimum spanning tree for a connected weighted graph. The algorithm aims to find a subset of the edges that forms a tree that includes every vertex.
• The total weight of all the edges in the tree is minimized. However, if the graph is not connected, then it finds a minimum spanning forest. Note that a forest is a collection of trees. Similarly, a minimum spanning forest is a collection of minimum spanning trees.
• Kruskal’s algorithm is an example of a greedy algorithm, as it makes the locally optimal choice at each stage with the hope of finding the global optimum.

Algorithm

 Step 1: Create a forest in such a way that each graph is a separate tree.
 Step 2: Create a priority queue Q that contains all the edges of the graph.
 Step 3: Repeat Steps 4 and 5 whileQis NOT EMPTY
 Step 4: Remove an edge from Q 
 Step 5: IF the edge obtained in Step 4 connects two different trees, then Add it to the forest (for combining two trees into one tree).
         ELSE
           Discard the edge
 Step 6: END

Explanation

• In the algorithm, we use a priority queue Q in which edges that have minimum weight takes a priority over any other edge in the graph.
• When the Kruskal’s algorithm terminates, the forest has only one component and forms a minimum spanning tree of the graph.
• The running time of Kruskal’s algorithm can be given as O(E log V), where E is the number of edges and V is the number of vertices in the graph.

---