A Minimum Spanning Tree (MST) of a weighted graph G(V, E) is a tree obtained by removing some edges in G such that the sum of the weights of the resulting tree's edges is as small as possible. In this notation, V is the set of vertices / nodes and E is the set of edges.
There are several algorithms for computing an MST. The two most popular ones are likely Prim's algorithm and Kruskal's algorithm. Prim's is usually used for dense graphs (a lot more edges than nodes), because of its O(|V|^2) complexity. Kruskal's is generally chosen for sparse graphs (number of edges is close to the number of nodes), because of its O(|E| log |E|) complexity.
But what if we are interested in the second-Minimum Spanning Tree (sMST)?
Fortunately, there's a simple algorithm that will work. First, we compute a classic MST using any algorithm. We just need a way of accessing the MST's edges. Let's refer to this set as ME.
Now, for each edge e=(u, v) in the original graph G that is not already part of the MST (so not part of ME), we will see what would happen if we added it to our MST. This would form a cycle. We will walk this cycle and determine the highest weight edge max_cycle_edge(e) that is not e. You can do this by walking up the parents of u and v until you reach a common ancestor. Don't actually add the edge, just pretend its there and do the computations.
This will give us a bunch of max_cycle_edge values (one for each edge e). We need the one that minimizes the expression weight(e)-weight(max_cycle_edge(e)). Once we find it, remove e from ME and add max_cycle_edge(e). This will be our sMST.
The time complexity for this is O(|E|*|V|), since we walk a cycle for each edge, accessing O(|V|) nodes for each edge.
To get an intuitive idea about why this works, consider what Kruskal's algorithm does: at each step, it adds the edge that:
- Does not create a cycle and
- Has minimum weight at that step.
This algorithm basically tries to add the second-minimum weight edge in step 2 above, but it has to consider all possibilities, and this is faster if we start from an MST.
Is there a faster way of doing this?