Question

Q2. (30 pts) Find the minimum spanning tree using Prim's algorithm for the following graph. For this question, the solution must be provided step by step as shown in your textbook in Figures 9.51 in page 415. 6 FRL B 4

C++ Data structure and algorithm

Graph Algorithms

Answer 1

Please find the step by step solution below.

Prim's Algorithme It produces a minimum spanning tree next minimum by selecting a vertex and add the on until all the edge from that vesten and so vertices are covered and no cycles are there? A Step 1:- choose a vertex Step 2 - Find all connected vertices of A AB-4 AC-2v (minimum) TA ? step 3:- Find all connected vertices of LA, C} AB-4 (BC - Dv (min.) CE-1 Janyone Stepa: & A,B,C} AB-4 BF-6 BD-2 BE-5 CE-1v (min) steps: SA, B, C, E} AB-9 BF-6 or TBD-27 BE-5 EG-9 EF-5 ED_3

SHEE Step-6 {A, B, C,D,E} 2 TAB-4 anext min. but BF-6 forms a cycle BES EG-9 EF-5V ED - 36 min. but formy DF-F a cycle Step 7: EA, B, C, D,E,F} 1 2 BF-6 » BE - 5 min but for EG-9 DF-7 TFG-3% Minimum spanning Tree for given graph G. Step 8: LA, B, C, D, E, F, G} V All vertices are covered. v No cycles.

If you have any doubts, please comment down here in the comment section below.

Please hit a like if you liked the answer. It really helps us. Happy Learning..!!