binary_eagle's blog

By binary_eagle, history, 4 years ago, In English,

Hi guys,

I have done some thinking about how to solve 2nd best Minimum Spanning Tree. I want to hear your suggestions on if its correct and how you would solve it. Thanks.

Let G = (V,E) be a graph. Lets assume we know how to solve the MST using Kruskal as that is trivial. At each step of Kruskal, consider an edge e=<a,b>.

If e does not cause a cycle then it is in MST Otherwise It can cause a cycle. Now consider all edges in such a cycle and take the biggest edge in the cycle e1.

Claim : If we maintain the value (e-e1) and minimize it over all cases where adding an edge will introduce a cycle then we would have the 2nd best MST by simply replacing e1 with e.

Is this true ? How would you solve this problem ?

Thanks.

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any ideas???

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have problems understanding your claim.

    Can you write it in psuedo code or elaborate a bit more?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, Let me try to elaborate on it more.

      I will try to say little about the general reasoning on Kruskal and then use that as a spring board for the claim.

      Each Iteration in Kruskals MST algorithm tries to add an edge from a priority queue to another set of edges that "must" be in the MST.

      Now consider such an iteration and let E=(a,b) be an edge from the priority queue. When we try to add E to the set of "must" spanning tree two cases come out

      Case 1: No cycles formed

      Case 2: A cycle is will be formed. So we don't add E. Consider such a cycle that "could have been formed" and let us denote it by e1-e2-e3-...-E. Where e1 = (b,x) and E=(a,b).

      my claim.

      What if we can calculate the difference of the weight on E and some other weight on one of the edges say the one with the largest weight.

      E.weight > ei.weight

      d = E.weight — ei.weight;

      If we minimize this value d over all iterations of Kruskals algorithm and then add

      d — ei.weight to the final value of the best MST, this will give us the second best MST.

      Hope its clearer now.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ok now I think I know what you mean.

        Your method is almost equivalent to a O(V2) algorithm I know.
        Except that there's a tiny issue with your idea.
        You need to minimize d over all edges, rather than iterations of Kruskals only. Fix that, and I think your idea should be correct :)

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

1) Build MST

2) Iterate over the edge(u, v). If this edge is in MST -> continue; else

find lca = LCA(u, v);

now u need to find maxEdge on path lca->u and maxEdge on path lca->v, it can be done using binary "ascent?".

define x = maxEdge. we update answer by value (InitMST + W(u, v) — x).

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I think you mean maximum edge since you want to minimize the quantity W(u,v) — x.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

First I Save All The Edges That are in my First MST

And Then Run The Kruskal Algo Again

And If This Edge was in The First MST I Put A Flag That Dont Use It And Then Get The MST And Then check

Another Edges And Ofcurse After Flagging any edge when i finish i make this edge free to use

vector<edge> Adjlist;
bool flag[MAX][MAX];
bool taken[MAX][MAX];
int MST(bool TheFirtMST) {

	for (int j = 0; j < MAX; j++)
		p[j] = j,r[j] = 1;

	for (int i = 0; i < Adjlist.size(); i++) {

		edge e = Adjlist[i]; 

			if(!flag[e.From][e.To]){

			if (!isSame(e.From, e.To)) {

				s += e.Cost;

				unionSet(e.From, e.To);

				if (TheFirtMST) {

					taken[e.From][e.To] = true;

				}
			}
			
			}
		}
	
	return s;

}
int main(){
First = MST(TheFirstMST);

    for (int j = 0; j < Adjlist.size(); j++) {


	edge e = Adjlist[j];

		if (taken[e.From][e.To]) {

	           flag[e.From][e.To] = 1;

			Second = MST(!TheFirstMST);

				if (Second >= First)

					Vec.push_back(Second);

				            flag[e.From][e.To] = 0;
			}
		}

}
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Seems i should write code to clarify my point/issue.

pq is priorityqueue S is edges in MST d is int

  1. Let S be set of edges in MST S=null 2.sort edges by putting them in priority queue

  2. while(number of components in union find != 1){

  3. x = pq.pop(); // get next edge

  4. if(same_set(x.first, x.second)){ //a cycle is formed if i add this edge g = get maximum edge from a traversal from x.first to x.second if x.w — g < d d = x.w — g } }

Let W be the final weight. Second best MST is W+d

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It turns out that my intuition was correct and that the only part missing for me is using LCA algorithm to find maximum distance on cycle.

For more info see http://codeforces.com/blog/entry/9570

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    You don't really need LCA for this one. I don't have the energy to explain it right now.
    However, consider doing a simple Prim/Kruskal algorithm first to find out an arbitrary MST,
    then do the minimization through all edges (not on the MST) afterwards.

    When you have the MST already, you can preprocess by starting from an arbitrary vertex and record on each vertex, the longest edge it has seen so far. This way, the query takes O(1) for each edge you check.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you can still do stuff with dsu to find that

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please elaborate a little on it.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ok now you have the Mst,
        let's say that the Mst's edges are in the array e[N]
        and we know that e[i].w <= e[i+1].w
        we have m — n + 1 queries which are like what is the longest edge's weight from u to v in the mst (the queries are the edges which are not in mst)
        now let's say that at first all vertices are in their own sets and we will add edges one by one and we will merge the two sets which are located at the endpoint of the edges (move the smaller one to the bigger one) and we will check the queries of the smaller one to see if there is any queries that goes from the smaller to the bigger one the answer of the query is this edge's weight
        the complexity is O(qlgn + nlgn)

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In conclusion and for sake of anyone that might read this for help sometime in the future. The intuition was correct as can be proved from induction. I have also used it to solve a problem on https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1541

The problem requires us to find first and second best MST. The algorithm i used works in O(ElgE + E + EV) time.

  1. While finding MST with kruskal, store edges not in MST and also note edges in MST.

  2. For each node (u,v) find the max path weight from u to v in the spanning tree lets call it path(u,v). This can be done in O(V) time since E=V-1.

  3. For each edge(a,b) not in MST, minimize the value w(a,b)-path(a,b) where w() is the weight on the edge.

  4. add the minimized value to the first mst and you get the value of the second best MST.