3.3k views
13 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 Sujata
by
7.6k points

1 Answer

4 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 Bosse Nilsson
by
8.2k points
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.