Answer to Question #247813 in Algorithms for John

Question

a. Use Prim’s algorithm starting at node A to compute the Minimum Spanning Tree (MST) of the following graph. In particular, write down the edges of the MST in the order in which Prim’s algorithm adds them to the MST. Use the format (node1; node2) to denote an edge.[8 marks]



b. For the same graph as above, write down the edges of the MST in the order in which Kruskal’s algorithm adds them to the MST.

Answer 1

a.

A Minimum Spanning Tree in an undirected connected weighted graph is a spanning tree of minimum weight (among all spanning trees). 

Prim’s Algorithm :

Start by picking any vertex to be the root of the tree.

While the tree does not contain all vertices in the graph find shortest edge leaving the tree and add it to the tree.

MST: $\{\{A,B\},\{B,C\},\{C,E\},\{E,H\},\{E,G\},\{H,F\}\}$

WEIGHT=46

b.

Kruskal's algorithm to find the minimum cost spanning tree uses the greedy approach. This algorithm treats the graph as a forest and every node it has as an individual tree. A tree connects to another only and only if, it has the least cost among all available options and does not violate MST properties.

Add the edge which has the least weightage:

$\{B,C\},\{B,A\},\{A,F\},\{A,G\},\{F,H\},\{H,E\},\{C,D\}$