# MST Of An Almost Tree

A graph $$G = (V,E)$$ is called an almost tree if it is connected and has most $$n + c$$ edges where $$n = |V|$$ and $$c$$ is a small constant number. How would I go about designing an algorithm for a given almost tree graph $$G$$ with distinct edge weight costs that computes a minimum spanning tree of $$G$$ in time $$O(n)$$?

• You can use LaTeX to typset mathematics, rather than doing it manually with italics. I edited to show you how; we also have a brief tutorial. – David Richerby Oct 17 '18 at 17:55
• I appreciate it -- looks more appropriate that way – Shandy Sulen Oct 17 '18 at 20:20

Here is the description of a desired algorithm in Python style pseudocode.

Generate a spanning tree T of G
Put all remaining edges that are not in T in a list L
For each edge e in L:
Find the cycle C in the graph that is T plus edge e.
If e is lighter than the heaviest edge e' in C:
add e to T and remove e' from T


It requires $$O(n)$$ operations to generate a spanning tree. It requires $$O(n)$$ operations to find a cycle when you add an edge to a tree and $$O(n)$$ operations to find the heaviest edge in a cycle. Since there were total $$c+1$$ edges remaining, where $$c+1$$ is a constant, the for loop requires $$O(n)$$ operations. Adding up other operations of small time, we find that the time-complexity of the algorithm is $$O(n)$$.

The correctness of the above algorithm has been proved in my answer to turn MST of G to MST of G with one new edge. Note that initially T is its own MST.