Prim's algorithm

Prim’s Algorithm

• Prim's Algorithm is a greedy approach that is used to find the Minimum Spanning Tree (MST) from a graph.

• To apply Prim’s algorithm, the given graph must be weighted, connected, and undirected.

• Prim's algorithm finds the subset of edges that includes every vertex of the graph such that the sum of the weights of the edges can be minimized.

• Prim's algorithm follows a greedy approach that starts from one vertex, explores all the adjacent nodes with all the connecting edges at every step, and continues to add the edges with the smallest weight until the goal is reached.

• The most important point is the edges with the minimal weights causing no cycles in the graph got selected.

Greedy Approach of Prim's Algorithm -

Step 1 -

• Check whether the graph contains any loops and parallel edges or not.
• If a graph contains any loops and parallel edges, then remove all loops and parallel edges.

Step 2 -

• Randomly choose any vertex, but the vertex connecting to the edge having the least weight is usually selected.

Step 3 -

• Find all the edges that connect the tree to new vertices.
• Find the least weight edge among those edges and include it in the existing tree.
• If including that edge creates a cycle, then reject that edge and look for the next least weight edge.

Step 4 -

• Keep repeating step - 3 until all the vertices are included and Minimum Spanning Tree (MST) is obtained.

Let's find out the minimum cost spanning tree for the given graph using Prim's Algorithm.

• In the given graph there are no loops and parallel edges are present.
• Therefore, no need for any type of removal.
• Directly start with selecting any random vertex.
• Here, we select Vertex 0 at first.

• Finally, we get all the vertices that have been included in the Minimum Spanning Tree, so stop here.

Now, calculate the Cost of the above Minimum Spanning Tree (MST)

$$ Cost\ of\ Minimum\ Spanning\ Tree\ = Sum\ of\ Weights\ of\ all\ edges\ of\ the\ MST $$

$$ = (0, 2) + (2, 5) + (5, 4) + (4, 1) + (1, 3) $$ $$ = 10 + 50 + 30 + 40 + 20 $$ $$ = 150\ Units $$

Thus, the Minimum Cost of the Spanning Tree for the given graph is 150 Units.