Using Prim’s and Kruskal’s Algorithm, find minimum spanning tree for following graph:

// solving using Prim’s Algorithm:

Step 1: draw the given graph.

Step2: remove all loops. Any edge that starts and ends at the same vertex is called a loop. In this case, there is no loop.

Step 3: remove all parallel edges two vertex except one with the least weight. In this case, there are no parallel edges.

Step 4: Create a table, where number of rows = number of columns = number of vertex in the graph.

Step 5: now, put 0 in cells having same row and column name.

Step 6: Now, Start filling other columns. Start with Vertex A. Find the edge that directly connects Vertex A and B. In this case, we have edge of weight 25 that directly connects A and B.

Step 7: put 25 in AB and BA.

Step 8: Repeat these steps for all the vertex that are directly connected.

Step 9: If any vertex is not connected directly, for eg: Vertex A and D; then put ∞(infinity symbol).

Here AD and DA will have ∞.

Table is now completely filled. Next Task is to find Minimum spanning Tree.

Step 10: Start from vertex A. Find the smallest value in row A

Smallest Value in row A is 10. Mark AF and FA and draw the graph.

Smallest Value in row B is 8. Mark BD and DB and draw the graph.

Smallest Value in row C is 15. Mark CB and BC and draw the graph.

Similarly, do for the all the rows and you will get the following table.

(Note: we will not consider 0 as it will correspond to the same vertex.)

So minimum spanning tree using prim’s algorithm is below:

Now, if connect DC, so it will form a ckt like below:

Therefore, we will skip this edges and select next edge FE.

Since our minimum spanning tree should be of 6 edges, so we will stop here and this is our MST.

// solving using kruskal’s algorithm:

Step 1: Remove all the loops. Any edge that starts and ends at the same vertex is a loop. In our case, it does not exist.

Step 2: remove all parallel edges two vertex except one with the least weight. In this case, we don’t have any parallel edges.

Step 3: Create the edge table. An edge table will have name of all the edges along with their weight in ascending order.

If you look at the graph, you will notice there are 9 edges in total, so our edge table will have 9 (nine) columns.

In our case, AB and DC both edges have weight 25 so we will consider both. And you can write them in any order i.e AB first then DC or vice versa.

Step 4: To find minimum spanning tree, number of edges will be

Number of edges=No. of vertices- 1

In our case, no. of vertices are 8, so our minimum spanning tree will have 7 edges.

Step 5: To find the MST, we will start with the smallest weight edge and keep selecting edges that does not form any circuit with the previously selected edges.

Since 7 is the smallest weight so we will select GD.

Drawing this edge GD