asked 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
asked
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.

answered
User Bosse Nilsson
by
8.2k points
Welcome to Qamnty — a place to ask, share, and grow together. Join our community and get real answers from real people.