Question

Which is the cost of the minimum spanning tree of the weighted graph using Kruskal's Algorithm?

28
30
31
40

Answer 1

9514 1404 393

Answer:

(a) 28

Explanation:

Kruskal's algorithm has you identify the shortest edge at each stage, including in the tree any identified edge that does not form a cycle. Here, we can start with AB, then add DF, EH, HG, BG, AC, CD and that covers the entire graph.

Starting at E, the node list is EHGBACDF. The cost is ...

3 +4 +5 +1 +6 +7 +2 = 28

__

In the attached, the minimum-cost spanning tree is highlighted in red.