Krukal\'s algorithm and Prim\'s algorithm questions Chegg will not accept my ima

ID: 3605923 • Letter: K

Question

Krukal's algorithm and Prim's algorithm questions

Chegg will not accept my image for some reason here is the share link if you would look at it.

https://imgur.com/DBKSB3s

this is graph H

MST stands for minimum spanding tree and will be used as such in the question, thanks

a) If we run Kruskal’s algorithm on H, what is the first edge added to the minimum spanning tree (MST).

b) please list the first seven edges of the MST in order from first to seventh

c) If we run Prim’s algorithm on H starting from the vertex 9, what are the first eight edges added to the MST. list from first to eighth

Note that H has 9 vertices and hence the minimum spanning tree of H will have 8 edges. The toal weight of the MST of H is [x].

Please write your answers in numbers only. What is the total weight of the MST?

Kruskal’s algorithm: Keep on adding the minimum edge in spanning tree until there is not any cycle.

Part-a:

First minimum edge of graph H is 6->7 which is 1, this will be the first edge added to the spaning tree.

Part-b:

order of edges: 1, 2, 3, 4, 5, 6, 8,13 (list from starting to ending)

as 7,9,10,11,12 and 14 edges are creating cycle , not inculded

Part-c:

Order of edges: 3, 4, 1, 8, 2, 5, 6, 13 (list from first to last)

Part-d:

total weight = 3+4+1+8+2+5+6+13 = 42

so total weight will be 42.

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.