Consider the undirected graph below:
Using Prim's algorithm to construct a minimum spanning tree starting with node a, which one of the following sequences of edges represents a possible order in which the edges would be added to construct the minimum spanning tree?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. (a,b), (b,c), (c,i), (c,f), (f,g), (g,h), (c,d), (d,e)
Explanation
From a: (a,b) 4; then (b,c) 8 (tie with (a,h) 8); (c,i) 2; (c,f) 4; (f,g) 2; (g,h) 1; (c,d) 7; (d,e) 9. Each step adds the cheapest edge leaving the tree, matching option C.
More Data Structures and Algorithms questions
- G T Let be a simple undirected graph, D be a DFS G T tree on , and B be the BFS tree on G. Consider the following statements. G Statement I…
- The weight of minimum spanning tree in graph G, calculated using Kruskal's algorithm is :
- What is the worst case running time of Insert and Extract-min, in an implementation of a priority queue using an unsorted array? Assume tha…
- In a B-Tree, each node represents a disk block. Suppose one block holds 8192 bytes. Each key uses 32 bytes. In a B-tree of order M there ar…
- Give tight bounds for T(n) = 4T(√n) + lg²n, with T(n) constant for n ≤ 2.
- Consider a weighted directed graph. The current shortest distance from source S to node x is represented by d[x]. Let d[v]= 29, d[u]= 15, w…