I'm writing an algorithm for finding the second min cost spanning tree. my idea was as follows:

Use kruskals to find lowest MST.
Delete the lowest cost edge of the MST.
Run kruskals again开发者_JAVA技巧 on the entire graph.
return the new MST.

My question is: Will this work? Is there a better way perhaps to do this?

You can do it in O(V²). First compute the MST using Prim's algorithm (can be done in O(V²)).

Compute max[u, v] = the cost of the maximum cost edge on the (unique) path from u to v in the MST. Can be done in O(V²).

Find an edge (u, v) that's NOT part of the MST that minimizes abs(max[u, v] - weight(u, v)). Can be done in O(E) == O(V²).

Return MST' = MST - {the edge that has max[u, v] weight} + {(u, v)}, which will give you the second best MST.

Here's a link to pseudocode and more detailed explanations.

Consider this case:

------100----
|           |
A--1--B--3--C
      |     |
      |     3
      |     |
      2-----D

The MST consists of A-B-D-C (cost 6). The second min cost is A-B-C-D (cost 7). If you delete the lowest cost edge, you will get A-C-B-D (cost 105) instead.

So your idea will not work. I have no better idea though...

You can do this -- try removing the edges of the MST, one at a time from the graph, and run the MST, taking the min from it. So this is similar to yours, except for iterative:

Use Kruskals to find MST.
For each edge in MST:
1. Remove edge from graph
2. Calculate MST' on MST
3. Keep track of smallest MST
4. Add edge back to graph
Return the smallest MST.

This is similar to Larry's answer.

After finding MST,

For each new_edge =not a edge in MST

Add new_edge to MST.
Find the cycle that is formed.
Find the edge with maximum weight in cycle that is not the non-MST edge you added.
Record the weight increase as W_Inc = w(new_edge) - w(max_weight_edge_in_cycle).
If W_Inc < Min_W_Inc_Seen_So_Far Then
- Min_W_Inc_Seen_So_Far = W_Inc
- edge_to_add = new_edge
- edge_to_remove = max_weight_edge_in_cycle

Solution from following link.
http://web.mit.edu/6.263/www/quiz1-f05-sol.pdf

slight edit to your algo.

    Use kruskals to find lowest MST.
    for all edges i of MST
        Delete edge i of the MST.
        Run kruskals again on the entire graph.
        loss=cost new edge introduced - cost of edge i
    return MST for which loss is minimum

Here is an algorithm which compute the 2nd minimum spanning tree in O(n^2)

First find out the mimimum spanning tree (T). It will take O(n^2) without using heap.
Repeat for every edge e in T. =O(n^2)
Lets say current tree edge is e. This tree edge will divide the tree into two trees, lets say T1 and T-T1. e=(u,v) where u is in T1 and v is in T-T1. =O(n^2)

Repeat for every vertex v in T-T1. =O(n^2)

Select edge e'=(u,v) for all v in T-T1 and e' is in G (original graph) and it is minimum
Calculate the weight of newly formed tree. Lets say W=weight(T)-weight(e)+weight(e')
Select the one T1 which has a minimum weight

Your approach will not work, as it might be the case that min. weight edge in the MST is a bridge (only one edge connecting 2 parts of graph) so deleting this edge from the set will result in 2 new MST as compared to one MST.

_{based on @IVlad's answer}

Detailed explanation of the `O(V² log V)` algorithm

Find the minimum spanning tree (MST) using Kruskal's (or Prim's) algorithm, save its total weight, and for every node in the MST store its tree neighbors (i.e. the parent and all children) -> O(V² log V)
Compute the maximum edge weight between any two vertices in the minimum spanning tree. Starting from every vertex in the MST, traverse the entire tree with a depth- or breadth-first search by using the tree node neighbor lists computed earlier and store the maximum edge weight encountered so far at every new vertex visited. -> O(V²)
Find the second minimum spanning tree and its total weight. For every edge not belonging to the original MST, try disconnecting the two vertices it connects by removing the tree edge with the maximum weight in between the two vertices, and then reconnecting them with the currently considered vertex (note: the MST should be restored to its original state after every iteration). The total weight can be calculated by subtracting the weight of the removed edge and adding that of the added one. Store the minimum of the total weights obtained.

To practice you could try the competitive programming problem UVa 10600 - ACM Contest and Blackout, which involves finding the second minimum spanning tree in a weighted graph, as asked by the OP. My implementation (in modern C++) can be found here.

MST is a tree which has the minimum weight total of all edges of the graph. Thus, 2nd minimum mst will have the 2nd minimum total weight of all edges in the graph.

let T -> BEST_MST ( sort the edges in the graph , then find MST using kruskal algorithm)

T ' -> 2nd best MST

let's say T has 7 edges , now to find T ' we will one by one remove one of those 7 edges and find a replacement for that edge ( cost of that edge definitely will be greater than the edge we just removed from T ).

let's say original graph has 15 edges

our best MST ( T ) has 7 edges

and 2nd best MST ( T ' ) will also going to have 7 edges only

How to find T '

there are 7 edges in T , now for all those 7 edges remove them one by one and find replacement for those edges .

let's say edges in MST ( T ) --> { a,b,c,d,e,f,g }

let's say our answer will be 2nd_BEST_MST and initially it has infinte value ( i know it doesn't sounds good , let's just assume it for now ).

for all edges in BEST_MST :

current_edge = i find replacement for that edge, replacement for that edge will definitely going to have have weight more than the ith edge ( one of 7 edges ) how we will going to find the replacement for that edge , using Kruskul algorithm ( we are finding the MST again , so we will use kruskal algorithm only , but this we don't have to sort edges again , because we did it when we were finding the BEST_MST ( T ). NEW_MST will be generated 2nd_best_MST = min( NEW_MST , 2nd_best_MST ) return 2nd_best_MST ALGORITHM

let' say orignal graph has 10 edges find the BEST_MST ( using kruskal algo) and assume BEST_MST has only 6 edges bow there are 4 edges remaining which is not in the BEST_MST ( because their weight value is large and one of those edges will give us our 2nd_Best_MST for each edge 'X' not present in the BEST_MST ( i.e. 4 edges left ) add that edge in out BEST_MST which will create the cycle find the edge 'K' with the maximum weight in the cycle ( other than newly_added_edge 'X' ) remove edge 'K' temporarily which will form a new spanning tree calculate the difference in weight and map the weight_difference with the edge 'X' . repeat step 4 for all those 4 edges and return the spanning tree with the smallest weight difference to the BEST_MST.