Question

Δ Drive myHR - + 90% 9. Use the Prims algorithm with a priority queue implemented as an unsorted array to find the miniam gon ning tree from the graph below. (a) At each iteration, illustrate the priority queue with information about a vertex weight and vertex parent for each vertex in the minimam spanning tree (b) Use the table to draw the minimum spanning tree. What is a weight of the minimum spanning tree? (c) Provide two examples for which you can get a solution using minimum spanning tree

Answer 1

Prim’s Algorithm to find the minimum cost spanning tree of a graph starting at vertex (A) as follows

Step 1: All the vertices connected to (A) will be considered

Edge	Cost	2
A-B	1(min)
A-F	6
A-G	5

Step 2: All the vertices connected to (A) & (B) will be considered

Edge	Cost	2
A-F	6
A-G	5
B-C	5
B-D	1(min)
B-E	6

Step 3: All the vertices connected to (A), (B) & (D) will be considered

.Edge	Cost	2
A-F	6
A-G	5(min)
B-C	5
B-E	6
D-C	7

Step 4: All the vertices connected to (A), (B) , (D) & (G) will be considered

Edge	Cost	2
A-F	6
B-C	5(min)
B-E	6
D-C	7
G-F	7

Step 5: All the vertices connected to (A), (B) , (C) , (D) & (G) will be considered

Edge	Cost	2
A-F	6(min)
B-E	6
D-C	7
G-F	7

Step 6: All the vertices connected to (A), (B) , (C) , (D) , (F) & (G) will be considered

Edge	Cost	2
B-E	6(min)
D-C	7
G-F	7

b) The Minimum spanning tree of a graph is

2

The Weight of minimum spanning tree of a graph is 24

c) For n- Vertices we get (n-1) Edges in MCST. Here in graph having 7 Vertices so we get 6 Edges

Which is Required minimum spanning tree of a graph