Consider the graph given below: Question: Use Kruskal’s algorithm to find a…

2017

Consider the graph given below:

Question: Use Kruskal’s algorithm to find a minimum spanning tree for the graph. Which option lists the tree edges in the order in which they are chosen?

  1. A.

    AD, AE, AG, GC, GB, BF

  2. B.

    GC, GB, BF, GA, AD, AE

  3. C.

    GC, AD, GB, GA, BF, AE

  4. D.

    AD, AG, GC, AE, GB, BF

Attempted by 387 students.

Show answer & explanation

Correct answer: C

Correct answer: GC, AD, GB, GA, BF, AE

Key idea: Kruskal’s algorithm sorts edges by increasing weight and skips any edge that would form a cycle.

  1. Pick GC with weight 2.

  2. Pick AD with weight 2.

  3. Pick GB with weight 3.

  4. Pick GA with weight 3; this connects the {G, C, B} component with the {A, D} component.

  5. Pick BF with weight 4 to include F.

  6. Pick AE with weight 4 to include E.

After these six edges, all seven vertices are connected and no cycle has been formed.

Final MST order: GC, AD, GB, GA, BF, AE.

Explore the full course: Coding For Placement