Author |
Topic: second minumum spanning tree (Read 4775 times) |
|
svarunsv84
Newbie
Posts: 4
|
 |
second minumum spanning tree
« on: Mar 14th, 2007, 2:53pm » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender: 
Posts: 1001
|
|
Re: second minumum spanning tree
« Reply #1 on: Mar 15th, 2007, 2:19am » |
Quote Modify
|
on Mar 14th, 2007, 2:53pm, svarunsv84 wrote: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. |
|
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
|
| « Last Edit: Mar 15th, 2007, 2:20am by TenaliRaman » |
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
brute_force
Newbie
Posts: 5
|
|
Re: second minumum spanning tree
« Reply #2 on: Jun 16th, 2007, 8:21am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
aki_scorpion
Newbie
Gender:
Posts: 13
|
|
Re: second minumum spanning tree
« Reply #3 on: Jul 8th, 2007, 10:59am » |
Quote Modify
|
Hi
Could some give the O(|E|^2) algo for second minimum spanning tree ..
|
|
IP Logged |
|
|
|
sk
Newbie
Posts: 45
|
|
Re: second minumum spanning tree
« Reply #4 on: Sep 6th, 2007, 6:42pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
wangzhen
Newbie
Posts: 21
|
|
Re: second minumum spanning tree
« Reply #5 on: Sep 6th, 2007, 9:07pm » |
Quote Modify
|
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);
}
}
|
|
IP Logged |
|
|
|
Xellos
Newbie
Posts: 1
|
|
Re: second minumum spanning tree
« Reply #6 on: Nov 14th, 2011, 1:10pm » |
Quote Modify
|
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).
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print