417,503 views
27 votes
27 votes
What is the weight of the minimum spanning tree for the graph above found using Kruskal's Algorithm? ​

What is the weight of the minimum spanning tree for the graph above found using Kruskal-example-1
User Lee Ballard
by
2.9k points

1 Answer

13 votes
13 votes

Answer:

39

Explanation:

Kruskal's Algorithm has you add edges in order of weight, from least to greatest, excluding edges that form loops, until all nodes are connected.

__

Here, the edges have weights ...

5 -- AD, CE

6 -- DF

7 -- AB, BE

8 -- BC, EF

9 -- BD, EG

11 -- FG

15 -- DE

The edges shown in bold are ones that can be added without creating loops. Their total weight is 5×2 +6 +7×2 +9 = 39.

The weight of the minimum spanning tree is 39.

User Angel Politis
by
2.6k points
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.