Run Prim starting from vertex g and Kruskal algorithms on th

Run Prim (starting from vertex g) and Kruskal algorithms on the graph below. For Prim\'s algorithm draw a table that shows the vertices in the queue at each iteration, similar to the example run in class. Prim\'s algorithm: using the table from the first part, list the order in which edges are added to the tree. Kruskal\'s algorithm: list the order in which edges are added to the tree.

Solution

In prim\'s algorithm we start with empty set F and fill vertex having minimum possible edge weight to that set and update weight of reaching neighbour vertices with minimum value.

In first step choose a, there are two neighbors of a and c has min weight edge so next will be c. Now b can be reached at cost = 1 from c, so choose b. Now d can be reached at cost 3 which is min among member of set F, so choose d. e can be reached in cost = 1, which is min among set members of F, so choose e. Then choose g because it has lesser cost of reaching then f, at last f with cost = 3.

Kruskal\'s we start with all vertices as different subtree. Start picking edge with min value and if connects two different subtree then add it out set F.

Firstly edge b-c and d-e both with weight 1 will get added to F since they both connect different subtree b,c and d,e respectively. Edge a-c with weight 2 will get added. Now b-d will get added with weight 3. Then f-g with weight 3 will get added. Now c-g with weight 6 will get added next because all other edges with weight lesser don\'t connect different subtrees except this.