For the weighted graph below, which of the following orders of adding edges can NOT be produced by a minimum spanning tree algorithm?
Edges (weight): a–b (1), d–f (1), b–f (2), c–d (2), b–c (3), d–e (3), b–d (4), c–e (4), e–f (5), a–c (6), c–f (7)
I. a-b II. d-f III. b-f IV. d-c V. d-e
Choose the correct answer from the options given below:
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. II, I, III, V, IV
Explanation
MST = {a-b, d-f, b-f, c-d, d-e}, weight 9. Kruskal must add edges in non-decreasing weight, so A, B and D are valid. C adds d-e (3) before d-c (2), which Kruskal never does. Prim cannot produce it either, since a-b is not adjacent to the tree {d, f}.More Data Structures and Algorithms questions
- Statement I: Given a graph G = (V, E) in which each vertex v ∈ V has an associated positive weight w(v), we can use linear programming to f…
- Assume that f(n), g(n) and h(n) are asymptotically positive. Which of the following is correct?
- The solution of the recurrence relation T(n) = 3T(n/4) + n log n is
- The number of nodes of height h in any n-element heap is at most
- Consider a B-tree of height h and minimum degree t ≥ 2 that contains n keys, n ≥ 1. Which of the following is correct?
- Which algorithm design approach is used in the quick sort algorithm?