Kruskal’s algorithm for finding a minimum spanning tree of a weighted graph G…
PYQ GATE 1991Modified — 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 61 students.
Sign up free to check your answer
Sign up freeLoading lesson…