Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

# DSA - Graphs and Hashing -Q6

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177
+1 vote

Suppose we run Prim's algorithm and Kruskal's algorithm on a graph G and the two algorithms produce minimum-cost spanning trees TP and TQ respectively, and TP is different from TK. Which of the following must be true?

(A)$.$ If e is a minimum cost edge in G, e belongs to both TP and TQ.

(B)$.$ If e is a maximum cost edge in G, e belongs to neither TP nor TQ.

(C)$.$ All edges in G have the same weight.

(D)$.$ Some pair of edges in G have the same weight

edited Oct 7, 2020