TADM2E 6.6

Special cases when adding an edge e = (u, v)
1) u or v not in the T's set of vertices, i.e. a vertex and an edge were added to G, include e' in T, return
2) T has an edge e' = (u, v) whose weight <= the weight of e, then e should not be included in T, return
3) T has an edge e' = (u, v) whose weight is > the weight of e, then replace e' with e, return

Include e in T, now T contains n vertices and n edges.
- Minimal spanning tree is connected => vertex U was reachable from V and V was reachable from U before adding e => now T contains a loop
Detect a loop using DFS(T)  # O(n + n) = O(2*n) = O(n)
Remove the edge with the highest weight from the loop so that the graph T becomes a minimal spanning tree again  # O(n)

--Bkarpov96 (talk) 12:17, 22 July 2020 (UTC)