CODEWITHSUNDEEP
algorithmkruskals-algorithmprims-algorithm
Tom Qiu
Tom Qiu

Reputation: 1

Special Case for MST algorithm in linear time

Let G = (V, E) be a weighted undirected connected graph, where all the edge weights are distinct. Let T denote the minimum spanning tree.

Suppose that G has m ≤ n + 157 edges. For this special case, give an MST algorithm that runs in O(n) time beating Kruskals and Prims algorithm.

Any hints?

Upvotes: 0

Views: 2234

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59174

First verify that the graph is connected.

Then repeat until the graph is a tree (# edges = n-1):

  • Find a cycle using DFS. There must be one since #edges >= n
  • Remove the longest edge in the cycle. It cannot be part of the MST.

When done you are left with the MST.

Even though this can take O(n) time per iteration, there will be at most 158 iterations, so that is still O(n) all together.

Upvotes: 0

Related Questions