Consider the following array a Starting with vertex v4 trace

Consider the following array: (a) Starting with vertex v4, trace through Prim\'s algorithm to find a minimum spanning tree for the graph represented by the array shown here. (b) Show the set of edges that compromise the minimum spanning tree. (c) What is the cost of the minimum spanning tree? Use Kruskal\'s algorithm (Algorithm 4.2) to find a minimum spanning tree for the graph in Exercise 2 as given below. Show the actions step by step.

Solution

prims solution-
set of edges-
{v4-v6},{v6-v1},{v1-v3},{v3-v2},{v2-v5}
Cost of MST-
40+35+72+71+73=291

kruskal sol-
set of edges of MST-
{v4,v8}-3
{v8,v9}-4
{v3,v7}-5
{v6,v10}-6
{v4,v5}-10
{v9-v10}-12
{v1-v4}-18
{v1-v2}-32
cost of MST-90