wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> second minumum spanning tree
        
(Message started by: svarunsv84 on Mar 14^th, 2007, 2:53pm)

Title: second minumum spanning tree
Post by svarunsv84 on Mar 14^th, 2007, 2:53pm

1) Given a graph and its minimum spanning tree. can u propose an algorithm to find the second minimum spanning tree.
A second minimum spanning tree is a tree whose total weight of the edges is greater than the minimum spanning tree and lesser than any other spanning tree of the graph.

2)Given a BST, find a value in it which is first greater than a number k.
For Ex in a BST
500
250 1000
25 375 750 1250

if k = 800, then the number to be returned is 1000.

Title: Re: second minumum spanning tree
Post by TenaliRaman on Mar 15^th, 2007, 2:19am

on 03/14/07 at 14:53:47, svarunsv84 wrote:

There is an obvious O(|E|^2) algorithm. I wonder if we can do better.

Quote:

2)Given a BST, find a value in it which is first greater than a number k.
For Ex in a BST
500
250 1000
25 375 750 1250

if k = 800, then the number to be returned is 1000.

The last left that you take.

-- AI

Title: Re: second minumum spanning tree
Post by brute_force on Jun 16^th, 2007, 8:21am

Quote:

2)Given a BST, find a value in it which is first greater than a number k.
For Ex in a BST
500
250 1000
25 375 750 1250

if k = 800, then the number to be returned is 1000.

In inorder traversal,print the number if its equal or greater than k+1

Title: Re: second minumum spanning tree
Post by aki_scorpion on Jul 8^th, 2007, 10:59am

Hi
Could some give the O(|E|^2) algo for second minimum spanning tree ..

Title: Re: second minumum spanning tree
Post by sk on Sep 6^th, 2007, 6:42pm

start from the minimum spanning tree
the next best would be the edge with a minimu difference with any of the present edges in the min spanning tree.
u can sort the edges not belnging to the spanning tree based on the difference of their value and the edge of the spanning tree from that vertex.
for each edge
u can remove the minimum spanning tree edge and insert this edge and check if it forms a cycle (just as in kruskal's algo).

for BST.
Traverse to the node which has value <= k
then the leftmost node of the right subtree shud give u the answer

Title: Re: second minumum spanning tree
Post by wangzhen on Sep 6^th, 2007, 9:07pm

For (2):

I have a solution with the time complexity
O(logn), but its space complexity is O(logn) too.

#define NON -1

int Find(BST *bst, int v){
int temp;
if(bst == NULL) return NON;
if(bst->value > v){
temp = Find(bst->leftchild, v);
if(temp == NON)
return bst->value;
return temp;
}
else{
return Find(bst->rightchild, v);
}
}

Title: Re: second minumum spanning tree
Post by Xellos on Nov 14^th, 2011, 1:10pm

This is a much harder problem than it seems, but it can be solved by this algorithm:
let G be the original graph, H the MST
consider an edge E (of G) && (not of H), connecting vertices V and U, we get the 2nd MST by adding E to H and removing the most expensive edge from H, which lies on the road between V and U (other than E)
greedy approach: try all possible E-s, you need to know the edge that must be removed - find the most expensive edges between all pairs of vertices beforehand, which makes it O(N^2+E).