Faster second-best MST algorithm?

Question

I am struggling with this.

We can get MST using Kruskal's algorithm or Prim's algorithm for the MST.

And for "second-best" MST, I can:

1. first get MST using either of the algorithm mentioned above.
2. For each V-1 of the optimal edge from the MST:
   a. first remove or flag the edge
   b. continue calculating MST without that edge
   c. compare and record down that "second-best" MST with previous iteration
3. In the end we have "second-best" MST

But this runs in O(VE) where V is num of vertex and E is number of edges.

How can get a speed up using Union-find disjoint set or LCA(lowest common ancester) ?

hints, pseodo code, or web links pointers.

Any help would be highly appreciated! Thanks:)

Rudderhead

Answer 1

I'll describe polylogarithmic solution to the problem. Let's introduce some definitions. We'll denote:

1. Set of graph's vertices by V, set of graph's edges by E and set of MST edges by T.
2. Edge of graph between vertices v and u by {v, u}.
3. Weight of edge e by W(e) and weight of MST by W(T).

Let's consider function MaxEdge(v, u), which is equal to the edge with the largest weight on the simple path between v and u that belongs to T. If there are several edges with maximum weight MaxEdge(v, u) can be equal to any of them.

To find the second best MST, we need to find such edge x = {p, q}, that:

1. x does not belong to T.
2. Function W(x) - W(MaxEdge(p, q)) is minimal possible.

It's possible to prove that the second best MST can be constructed by removing MaxEdge(p, q) from T and then adding x = {p, q} to T.

Now let's build a data structure that will be able to compute MaxEdge(p, q) in O(log|V|).

Let's pick a root for the tree T (it can be any vertex). We'll call the number of edges in the simple path between vertex v and the root - the depth of vertex v, and denote it Depth(v). We can compute Depth(v) for all vertices in O(|V|) by depth first search.

Let's compute two functions, that will help us to calculate MaxEdge(p, q):

1. Parent(v, i), which is equal to the vertex that is a parent (might be non direct parent) of vertex v with depth equal to Depth(v) - 2^i.
2. MaxParentEdge(v, i), which is equal to MaxEdge(v, Parent(v, i)).

Both of them can be computed by a recurrence function with memorisation in O(|V|log|V|).

// Assumes that 2^i <= Depth(v)
Vertex Parent(Vertex v, Vertex i) {
    if (i == 0) return direct_parent[v];
    if (Memorized(v, i)) return memorized_parent[v][i]; 
    memorized_parent[v][i] = Parent(Parent(v, i - 1), i - 1);
    return memorized_parent[v][i];
}

Edge MaxParentEdge(Vertex v, Vertex i) {
    if (i == 0) return Edge(v, direct_parent[v]);
    if (Memorized(v, i)) return memorized_parent_edge[v][i]; 
    Edge e1 = MaxParentEdge(v, i - 1);
    Edge e2 = MaxParentEdge(Parent(v, i - 1), i - 1);
    if (W(e1) > W(e2)) {
        memorized_parent_edge[v][i] = e1;
    } else {
        memorized_parent_edge[v][i] = e2;
    }
    return memorized_parent_edge[v][i];
}

Before we are ready to compute MaxEdge(p, q), let's introduce the final definition. Lca(v, u) will denote lowest common ancestor of vertices v and u in the rooted tree T. There are a lot of well known data structures that allows to compute Lca(v, u) query in O(log|V|) or even in O(1) (you can find the list of articles at Wikipedia).

To compute MaxEdge(p, q) we will divide the path between p and q into two parts: from p to Lca(p, q), from Lca(p, q) to q. Each of these parts looks like a path from a vertex to some of its parents, therefore we can use our Parent(v, i) and MaxParentEdge(v, i) functions to compute MaxEdge for these parts.

Edge MaxEdge(Vertex p, Vertex q) {
    Vertex mid = Lca(p, q);
    if (p == mid || q == mid) {
       if (q == mid) return QuickMaxEdge(p, mid);
       return QuickMaxEdge(q, mid);
    }
    // p != mid and q != mid
    Edge e1 = QuickMaxEdge(p, mid);
    Edge e2 = QuickMaxEdge(q, mid);
    if (W(e1) > W(e2)) return e1;
    return e2;
}

Edge QuickMaxEdge(Vertex v, Vertex parent_v) {
    Edge maxe = direct_parent[v];
    string binary = BinaryRepresentation(Depth(v) - Depth(parent_v));
    for (int i = 0; i < binary.size(); ++i) {
        if (binary[i] == '1') {
            Edge e = MaxParentEdge(v, i);
            if (W(e) > W(maxe)) maxe = e;
            v = Parent(v, i);
        }
    }
    return maxe;
}

Basically function QuickMaxEdge(v, parent_v) does jumps of length 2^i to cover distance between parent_v and v. During a jump it uses precomputed values of MaxParentEdge(v, i) to update the answer.

Considering that MaxParentEdge(v, i) and Parent(v, i) is precomputed, MaxEdge(p, q) works in O(log|V|), which leads us to an O(|E|log|V|) solution to the initial problem. We just need to iterate over all edges that does not belong T and compute W(e) - MaxEdge(p, q) for each of them.

Mayapple

Answer 2

Let V be the vertex set and E be the edge set.

Let T be the MST obtained using any of the standard algorithms.

Let maxEdgeInPath(u,v) be the maximum edge on the unique path in T from vertex u to vertex v.

For each vertex u perform BFS on T. This gives maxEdgeInPath(u,x) for all x belonging to V-u.

Find an edge (x,y) which does not belong to T that minimizes w(x,y) - w(maxEdgeInPath(x,y))

Weight of 2ndMST is W(T) + w(x,y) - maxEdgeInPath(x,y)

This is based on the algorithm provided in this link. I'm not sure if this is correct and I hope someone would add a proof here.

Compexity: To compute BST for 1 vertex takes O(V+E) = O(V) as E = V-1 in T Hence overall time complexity is O(V^2)

Gassing

Answer 3

#include <iostream>
#include <conio.h>
using namespace std;

#define ROW 7
#define COL 7
#define infi 5000  //infi for infinity
class prims
{
   int graph[ROW][COL],nodes;
   public:
   prims();
   void createGraph();
   void primsAlgo();
   bool checkforcrossline(int*,int,int);
};

prims :: prims(){
     for(int i=0;i<ROW;i++)
       for(int j=0;j<COL;j++)
     graph[i][j]=0;
}

void prims :: createGraph(){
    int i,j;
    cout<<"Enter Total Nodes : ";
    cin>>nodes;
    cout<<"\n\nEnter Adjacency Matrix : \n";
    for(i=0;i<nodes;i++)
        for(j=0;j<nodes;j++)
        cin>>graph[i][j];

    //Assign infinity to all graph[i][j] where weight is 0.
    for(i=0;i<nodes;i++){
        for(j=0;j<nodes;j++){
           if(graph[i][j]==0)
          graph[i][j]=infi;
        }
    }
}

void prims :: primsAlgo(){
    int selected[ROW],i,j,ne; //ne for no. of edgesintfalse=0,true=1,min,x,y;
    int min,x,y;
    int Answer=0;
    for(i=0;i<nodes;i++)
       selected[i]=false;

    selected[0]=true;
    ne=0;

    while(ne < nodes-1){
       min=infi;

       for(i=0;i<nodes;i++)
       {
          if(selected[i]==true)
          {
              for(j=0;j<nodes;j++)
              {
                if(selected[j]==false)
                {
                    if((min > graph[i][j]) && checkforcrossline(selected,i,j))
                    {
                        min=graph[i][j];
                        x=i;
                        y=j;
                    }
                }
            }
          }
       }
       selected[y]=true;
       cout<<"\n"<<x+1<<" --> "<<y+1;
       Answer+=graph[x][y];
       ne=ne+1;
    }
    cout<<"\nCost : "<<Answer ;
}

bool prims :: checkforcrossline(int* selectedArr,int n1,int n2)
{
    int big,small;
    if(n1>n2)
    {
        big=n1;small=n2;
    }
    else
    {
        big=n2;small=n1;
    }

    int restNodes[ROW];
    int count=0;
    for(int i=0;i<small;i++)
    {
        if(selectedArr[i]==true)
            {
                restNodes[count]=i;
                count++;
            }
    }
    for(int j=big+1;j<nodes;j++)
    {
         if(selectedArr[j]==true)
            {
                restNodes[count]=j;
                count++;
            }
    }


    int start=small+1;
    int end = big;
    for(;start<end;start++)
    {
        if(selectedArr[start] == true)
        {
            for(int find=0;find<count;find++)
            {
                if(graph[start][restNodes[find]]!= infi)
                    return false;
            }
        }
    }
    return true;
}

int main(){
    prims MST;

    cout<<"\nPrims Algorithm to find Minimum Spanning Tree\n";
    MST.createGraph();
    MST.primsAlgo();
return 0;
}

Bullis

if you can add a psedocode it would be more appropriate and people can easily understand your answer. – Gassing

Answer 4

Set ∆|T| = ∞.
Set Enew = −1, and Eold = −1.
For every edge e that is not on the tree, do:
- Add the edge to the tree, creating a cycle.
- find k the maximum weight edge in the cycle such that k != e.
- remove k
- compute the change in the tree weight δ = weight(e) − weight(k).
- if δ < ∆|T| then ∆|T| = δ and Enew = e and Eold = k.
The new tree is the one that results in from replacing Eold by Enew.

The running time is proportional to the number of edges

source:
http://web.mit.edu/6.263/www/quiz1-f05-sol.pdf

Chokefull

Answer 5

Refer this solution: http://web.mit.edu/6.263/www/quiz1-f05-sol.pdf

Here it needs to add another point, after adding an edge and calculating the maximum weighted edge in the cycle formed and thus finding the difference between the new and the old edge, that we need to keep a track of the edge that is causing the difference to be minimum. That particular edge can be added to form a second best minimum spanning tree.

Hambrick