380,093 views
35 votes
35 votes
Hi can someone may help me with this problem I'm struggling with
ASSP

Hi can someone may help me with this problem I'm struggling with ASSP-example-1
User Adil Saju
by
2.5k points

1 Answer

27 votes
27 votes

Answer:

see attached

cost = 33

Explanation:

Kruskal's Algorithm is a "greedy" algorithm that adds the next minimum-weight edge to the tree, provided that it does not create a loop.

__

The minimum-weight edge in the graph is DF, with weight 1.

The next minimum-weight edge is GH, with weight 2.

The next minimum-weight edge is AB, with weight 3.

The next minimum-weight edge is EF, with weight 4.

Edge DE is the next lowest-weight, but it creates a loop (DEF), so we ignore it.

BC is the next edge we'll add to our tree.

FG is the next edge we'll add to the tree.

Edge DG creates a loop, so we ignore it.

Edge FH creates a loop, so we ignore it.

CF is the next edge we'll add to the tree. This completes the minimum spanning tree using Kruskal's Algorithm.

Included edges are AB, BC, CF, DF, EF, GF, GH.

The cost of the tree is 3+6+10+1+4+7+2 = 33.

Hi can someone may help me with this problem I'm struggling with ASSP-example-1
User Dinidu Hewage
by
2.8k points