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
4.2k 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
4.4k points