Discrete Mathematical Structures

 

UNIT-3

Prim's Algorithm

Prim's Algorithm is used to find the minimum spanning tree from a graph. 

Spanning tree : A tree T is said to be spanning tree if  it contains all the vertices and do not form any cycles. i.e.  without forming any cycles a tree can be constructed and must have all the vertices. 

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 starts with the single node and explore all the adjacent nodes with all the connecting edges at every step. The edges with the minimal weights causing no cycles in the graph got selected.

The algorithm is given as follows.

Algorithm

• Step 1: Select a starting vertex
• Step 2: Repeat Steps 3 and 4 until there are fringe vertices
• Step 3: Select an edge e connecting the tree vertex and fringe vertex that has minimum weight
• Step 4: Add the selected edge and the vertex to the minimum spanning tree T
  [LOOP ENDS]
• Step 5: EXIT

Example :

Construct a minimum spanning tree of the graph given in the following figure by using prim's algorithm.

Step 1 : Choose a starting vertex B.

Step 2: Add the vertices that are adjacent to A. the edges that connecting the vertices are shown by dotted lines.

Step 3: Choose the edge with the minimum weight among all. i.e. BD and add it to MST. Add the adjacent vertices of D i.e. C and E.

Step 3: Choose the edge with the minimum weight among all. In this case, the edges DE and CD are such edges. Add them to MST and explore the adjacent of C i.e. E and A.

Step 4: Choose the edge with the minimum weight i.e. CA. We can't choose CE as it would cause cycle in the graph.

The graph produces in the step 4 is the minimum spanning tree of the graph shown in the above figure.

The cost of MST will be calculated as;

cost(MST) = 4 + 2 + 1 + 3 = 10 units.