0
304views
Explain the concept of greedy technique for Prim's algorithm. Obtain minimum cost spanning tree for the graph below Prim's algorithm.

Prim's algorithm

0
14views

## 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.
$$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$$