Algorithms - Algorithm Design Techniques
- Option : A
- Explanation : O(m + n) Because, edges are sorted so , no need to make min heap, so deletion from min heap time is saved.
You must be logged in to post a comment.
- Option : D
- Explanation : Ordering the weights, the sequence obtained is 1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 7 Now, in order to obtain minimum spanning tree using Kruskal's algorithm, we have to add edges with weights in increasing order such that weight of the spanning tree is minimum. In option (D), weights of the edges are 1, 1, 2, 3, 2 which contradicts Kruskal's algorithm.
You must be logged in to post a comment.
You must be logged in to post a comment.
- Option : D
- Explanation : In Kruskal’s Algorithm we choose on edge of G
which has smallest weight among the edges of G.
So (b, e) = 2, (e, f) = 3, (b, c) = 4, (a, c)= 8, (f,g) = 4
(c,d) = 5
Alternately
Order the edges in non-decreasing order and pick
edge one by one until all the nodes are completed
with no edge making cycle on addition.
You must be logged in to post a comment.
You must be logged in to post a comment.
- Option : B
- Explanation :
nodes are include in order
⇒ (P, O, R, U, S, T)
You must be logged in to post a comment.
You must be logged in to post a comment.
- Option : D
- Explanation : Using binary heap it requires O((|E| + |V|)log|V|)
You must be logged in to post a comment.
You must be logged in to post a comment.
You must be logged in to post a comment.