Question

Apply Kruskal' algorithm to find a minimum spanning tree of the graph in the following figure-Display **** of each step of the algorithm.

Describe the insertion sort algorithm. Compute its asymptotic time complexity for worst case and average case.

Answer 1

The given graph is name the vertices as shown.

To find minimum spanning tree of the given graph :-

Edges in increasing order of weights

Step 1 Add ‘BC’

Step 4 Add ‘EH’

Step 5 Add ‘AB’

Step 6 Add ‘AD’

STEP 7 Add 'DG'

STEP 8 Add 'FI’

Cost of the spanning Tree= 1+2+2+1+3+1+3+1=14 This

is the required spanning tree of the given graph.