Question-50

Algorithms

MCST

Suppose we run Prim’s algorithm and Kruskal’s algorithm on a graph G which have edges with distinct weights and these two algorithms produce minimum-cost spanning trees \(T_P\) and \(T_K\), with total minimum cost \(C_p\) and \(C_k\) respectively. Which of the following is true?

\(T_P\) and \(T_K\) are always the same but \(C_p\) may not be equal to \(C_k\)
\(T_P\) may be different to \(T_K\) but \(C_p\) is always equal to \(C_k\)
\(T_P\) and \(T_K\) are always the same and \(C_p\) is always equal to \(C_k\)
\(T_P\) may be different to \(T_K\) and \(C_p\) may not be equal to \(C_k\)

Answer

\(T_P\) and \(T_K\) are always the same but \(C_p\) may not be equal to \(C_k\)
\(T_P\) may be different to \(T_K\) but \(C_p\) is always equal to \(C_k\)
\(T_P\) and \(T_K\) are always the same and \(C_p\) is always equal to \(C_k\)
\(T_P\) may be different to \(T_K\) and \(C_p\) may not be equal to \(C_k\)