Kruskal's algorithm builds the MST by
Astarting at any vertex and growing one tree by the cheapest crossing edge
Brunning DFS twice on the graph
Csorting edges by weight ascending and adding each that doesn't create a cycle
Drunning Dijkstra from every vertex
Answer & Solution
Correct answer: C. sorting edges by weight ascending and adding each that doesn't create a cycle
Kruskal's strategy: sort the edge list, scan ascending, add each edge unless it closes a cycle with edges already accepted. Stop when |V| − 1 edges are picked. Starting at one vertex and growing one tree is Prim's strategy. Dijkstra solves shortest paths, not MST. Two DFS calls don't yield an MST.
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