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)$?
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.