186k views
10 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

1 Answer

12 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 Godvsdeity
by
8.3k points

Related questions

asked Jul 7, 2024 161k views
Mlemos asked Jul 7, 2024
by Mlemos
8.5k points
2 answers
2 votes
161k views
asked Jul 27, 2024 52.6k views
RHarris asked Jul 27, 2024
by RHarris
8.7k points
2 answers
4 votes
52.6k views