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?
5
-
Possible hint: perhaps the trick here is to prove that one of the standard approaches (Kruskal, Prim, Boruvka, ?..) works in linear time.Gassa– Gassa2021-12-21 17:16:21 +00:00Commented Dec 21, 2021 at 17:16
-
i tried to prove the (|V|+99)log|V|<=|V|+|V|+99 but its not true for every |V|Eyas Zidan– Eyas Zidan2021-12-21 17:19:20 +00:00Commented Dec 21, 2021 at 17:19
-
Yeah; so maybe try something other than Kruskal then...Gassa– Gassa2021-12-21 17:23:40 +00:00Commented Dec 21, 2021 at 17:23
-
For example, if it was true that the priority queue in Prim contains at most 99 elements at each moment, that would automatically mean linear time.Gassa– Gassa2021-12-21 17:24:58 +00:00Commented Dec 21, 2021 at 17:24
-
Even if not, the attempt in that direction can give some insight.Gassa– Gassa2021-12-21 17:25:43 +00:00Commented Dec 21, 2021 at 17:25
Add a comment
|
1 Answer
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.
10 Comments
Kelly Bundy
Can a cycle of degree-2 vertices actually exist here?
Matt Timmermans
If it's the whole graph after removing the degree-1 vertexes (which, of course implies |E| < |V| + 99), then yes. But I also wanted to allow for constructing a spanning forest of a disconnected graph.
Kelly Bundy
Ok, so not for the given problem, right?
Matt Timmermans
Well, sure... but that is expecting the OP to have been super careful with his problem statement, and they usually aren't.
Kelly Bundy
About the last step: I think there can be more than 100 nodes. Like a cycle/circle of 198 nodes, plus 99 additional edges connecting each node with the node "on the opposite side of the circle.
|