Kruskal’s algorithm for finding a minimum spanning tree of a weighted graph G…
GATE · 1991 · CS · Question 3 subpartsModified — slightly modified from the official paper; see the solution
Kruskal’s algorithm for finding a minimum spanning tree of a weighted graph G with n vertices and m edges has which tightest listed worst-case time complexity? Assume a simple graph and comparison sorting of edges.
- A.
O(n²)
- B.
O(mn)
- C.
O(m + n)
- D.
O(m log n)
- E.
O(m²)
Attempted by 18 students.
Sign up free to check your answer
Sign up freeLoading lesson…