Subject: Analysis Of Algorithm

Topic: Greedy Method

Difficulty: High

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 1 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 $$

$$ = (1, 2) + (2, 7) + (2, 3) + (3, 4) + (4, 5) + (5, 6) $$ $$ = 30 + 14 + 16 + 12 + 22 + 25 $$ $$ = 119\ Units $$

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