Question

Which of the graphs below correctly use Kurshal's Algorithm to determine a minimum spanning tree?

Answer 1

Answer:

  C

Step-by-step explanation:

Conveniently, the edges have weights that are sequential numbers 1 to 9, so according to Kruskal's algorithm we can examine them in order by weight until we find a 5-branch tree connecting all 6 nodes. (We throw out any branches that cause the tree to have a cycle.)

The branches with weights 1-4 form no cycles, so we can include those branches in our tree. The branch with weight 5 (DE) introduces a cycle (ABCEDA), so we ignore that branch. The next branch has weight 6 and forms no cycles, so it completes the 5 branches we need for our tree.

The result is the tree that matches diagram C.

_____

The diagram of A is not a tree. It contains a branch.

The diagram of B is a tree, but has total weight 20, which is more than the total weight of 16 of the tree in diagram C. Hence the tree of B is not minimal, nor was it found using Kruskal's algorithm.