Hi can someone may help me with this problem I'm struggling withASSP
1 answer:
Answer:
see attached
cost = 33
Step-by-step 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.
You might be interested in