We're given $T$ a minimal spanning tree (MST) of a non-directed, connected graph $G=(V,E)$ with non-negative weights for each edge $e \in E$. Let $e^* \in T$ be an edge in $T$ and let $G'=(V,E')$ be the graph which we get after removing $e^*$ ($E'=E\setminus \{e^*\}$). $G'$ is also connected.
I need to propose an algorithm which will run in $O(|E|)$ time and will restore $T$ such that it will yield an MST $T'$ for $G'$.
I'm really not sure if I'm in the right direction but this is what I thought of:
Let $e^*=(u,v)$.
a) We mark $e^*$ and remove it from $T$ and b) find the connected component of node $v$ by using BFS algorithm on $T$.
Now we have 2 connected components:
- the first starts from $v$ let's call it $S = T\setminus e^*$
- the second is $V\setminus S$
Clearly $e^*\notin S$ and $e^* \notin V\setminus S$. Also $S\neq V$ because otherwise we'd get a connected graph after the removal of $e^*$ of $n-1$ edges which would mean that there were $n$ edges in $T$ which is a contradiction since $T$ is a tree.
c) Then we start looking for a minimal edge $e'$ from $u\in V\setminus S$ to $v\in S$.
d) Once we found $e'$ we'll add it to $T$ and we'll get $T'$.
I'm having trouble with running times.
a) we need to traverse $G$ in order to find $e^*$ so it's the running time of BFS which is $O(|E|+|V|)$ and because $G$ is connected ($|E| \ge |V|-1$) then the time is $O(|E|)$.
b) BFS again so $O(|E|)$.
c) This could also be $O(|E|)$ because in the worst case the graph could be something like this:
d) is O(1).