Find numbers of necessary edges of a graph for all Minimal Spanning trees

Question

Given a undirected weighted graph, it's easy to find one MST(Minimal Spanning tree) by Kruskal's or Prim's algorithm. Consider all MST, there are three types of edge in the graph, edges that exist in all MST, edges that exist in at least one MST but not all MST and edges that do not exist in any MST. Is there any algorithm to find numbers of three types of edges not using recursion?

Answer 1

Definitely there is a simple approach to classify each edge $e$. Firstly build MST $T$. Then delete $e$ from the graph, and build MST $T'$ again. If it has greater weight $w(T') > w(T)$, then $e$ has the first type (appears in all MSTs). Otherwise, contract ends of the edge $e$, and build MST $T''$ in the new graph. If $w(T'') + w(e) = w(T)$, then $e$ has the second type (appears in at least one MST, but not in all), otherwise it has the third type (doesn't appear in any MST). It takes $\mathrm O(m^2 \log n)$, where $n$ is the number of vertices and $m$ is the number of edges.

However we can do it faster. Let's modify Kruskal's algorithm in the following way. Firstly sort all edges in non-decreasing weight order. Then every time we do the following. We add all edges of the same minimum weight together. Now all bridges have the first type, all other non-self-loops have the second type and all self-loops have the third type. After that we contract every component to a single vertex (using disjoint set data structure) before considering the next portion of edges. If we keep a list of non-isolated vertices, then we can classify all $m_i$ edges of the same weight using $\mathrm O(m_i \cdot \alpha(n))$ of time, where $\alpha(\cdot)$ is inverse Ackermann function. Here the total time is $\mathrm O(m \log m + \sum_i m_i \alpha(n)) = \mathrm O(m \log n + m \alpha(n)) = \mathrm O(m \log n)$.