CODEWITHSUNDEEP
algorithmgraph-theory
Eyas Zidan
Eyas Zidan

Reputation: 21

linear time algorithm for mst given |E|=99+|V|

I need to make a linear algorithm for finding minimal spanning tree given an undirected weighted and connected graph(with no isolated verities) the has |V| vertices and |V|+99 edges I think the solution should be based on Kruskal and divide an concur but no luck till now, any ideas?

Upvotes: 1

Views: 99

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59144

First remove all vertexes of degree 1, and add their adjacent edges to the MST until there are no more vertexes of degree 1.

Then consider each chain of degree-2 vertices. If a chain is a cycle, then add all but the most expensive edge to the MST.

Otherwise, the chain must run between two vertexes of degree >= 3. Replace the chain with a single edge. The cost of this edge will be the cost of the most expensive edge in the chain. That is the difference in cost between connecting the two ends via the chain instead of just connecting the vertexes to the ends.

Now you're left with vertexes of degree >=3. There must be less than 200 of those, and less than 300 edges remaining. Run Kruskal's to determine which edges go in the MST.

Upvotes: 2

Related Questions