prims and kruskal algorithm

Prim's Algorithm

Prim's algorithm is a greedy algorithm used to find the minimum spanning tree (MST) of a weighted undirected graph. The MST is a tree that spans all the vertices of the graph with the minimum total weight.

The steps of Prim's algorithm are as follows:

  1. Initialize: Start with an empty MST and select an arbitrary vertex as the starting point.
  2. Select the Minimum Weight Edge: Find the minimum weight edge that connects a vertex in the MST to a vertex outside the MST. Add this edge to the MST.
  3. Update the MST: Add the newly selected vertex to the MST.
  4. Repeat Steps 2 and 3: Repeat steps 2 and 3 until all vertices are included in the MST.

The algorithm terminates when all vertices are included in the MST.

Kruskal's Algorithm

Kruskal's algorithm is another greedy algorithm used to find the minimum spanning tree (MST) of a weighted undirected graph. Like Prim's algorithm, Kruskal's algorithm also finds the MST with the minimum total weight.

The steps of Kruskal's algorithm are as follows:

  1. Initialize: Start with an empty MST and sort all the edges of the graph in non-decreasing order of their weights.
  2. Select the Minimum Weight Edge: Select the edge with the minimum weight from the sorted list of edges.
  3. Check for Cycle: If adding the selected edge to the MST creates a cycle, discard the edge. Otherwise, add the edge to the MST.
  4. Repeat Step 2 and 3: Repeat steps 2 and 3 until all vertices are included in the MST.

The algorithm terminates when all vertices are included in the MST.

Both Prim's and Kruskal's algorithms guarantee the construction of a minimum spanning tree, but they differ in their approach. Prim's algorithm starts with a single vertex and grows the MST by adding the minimum weight edges, while Kruskal's algorithm starts with all vertices as separate trees and merges them by adding the minimum weight edges.

[1]