Per the lecture's guidance, choose Kruskal over Prim when
Athe graph has negative edge weights
Bthe source vertex is fixed in advance
Cyou need shortest paths from a single source
Dthe graph is sparse and the edge list is natural
Answer & Solution
Correct answer: D. the graph is sparse and the edge list is natural
On sparse graphs Kruskal's O(E log V) wins because sorting a small edge list is cheap. On dense graphs (E close to V²) Prim with a Fibonacci heap gives O(V²), beating Kruskal's O(V² log V). Negative weights and source vertices are irrelevant for MST; shortest-path-from-source is Dijkstra, a different algorithm.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for