首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >更快的次优MST算法?

问更快的次优MST算法?
EN

Stack Overflow用户
提问于 2014-03-01 03:14:55
回答 5查看 5.8K关注 0票数 9

我在为这件事而挣扎。

对于MST,我们可以使用Kruskal算法或Prim算法得到MST。

对于“第二好”MST,我可以:

  1. 首先,使用上述任何一种算法获得MST。
  2. 对于来自MST的每一个V-1最优边缘: 首先移除或标记边缘 b.继续计算无边MST c.与之前的迭代比较并记录“次优”MST。
  3. 最后,我们得到了“第二名”的MST。

但这在O(VE)中运行,其中V是顶点的num,E是边的数。

如何使用Union-查找不相交集或LCA(最低公共连接程序)来加快速度?

提示、pseodo代码或web链接指针。

任何帮助都将不胜感激!谢谢:)

EN

回答 5

Stack Overflow用户

发布于 2015-10-14 00:23:53

我将描述这个问题的多对数解。让我们介绍一些定义。我们将表示:

  1. 图的顶点集由V表示,图的边集由E表示,图的边集由T表示。
  2. 顶点v和u之间的图的边用{v, u}表示。
  3. 边缘e的权重W(e)法,MST的权重W(T)法。

让我们考虑函数MaxEdge(v, u),它等于在v和u之间属于T的简单路径上具有最大权重的边。如果有几个边的最大重量,MaxEdge(v, u)可以等于它们中的任何一个。

要找到第二好的MST,我们需要找到这样的边缘x = {p, q},即:

  1. x不属于T。
  2. 函数W(x) - W(MaxEdge(p, q))是最小的可能。

通过将MaxEdge(p, q)从T中移除,然后将x = {p, q}添加到T中,可以证明次优MST的构造是可行的。

现在,让我们构建一个能够在O(log|V|)中计算O(log|V|)的数据结构。

让我们为树T选择一个根(它可以是任何顶点)。我们将调用顶点v和根之间的简单路径中的边数--顶点v的深度,并表示为Depth(v)。我们可以用Depth(v)计算O(|V|)中所有顶点的深度优先搜索。

让我们计算两个函数,这将帮助我们计算MaxEdge(p, q)

  1. Parent(v, i),它等于顶点v的父级(可能是非直接父级)的顶点,深度等于Depth(v) - 2^i。
  2. MaxParentEdge(v, i),它等于MaxEdge(v, Parent(v, i))。

这两种方法都可以用O(|V|log|V|)记忆的递归函数计算。

代码语言:javascript
复制
// 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];
}

在我们准备好计算MaxEdge(p, q)之前,让我们先介绍最后的定义。Lca(v, u)将表示根树T中顶点v和u的最低共同祖先。有许多众所周知的数据结构允许在O(log|V|)甚至O(1)中计算O(log|V|)查询(您可以在维基百科上找到文章列表)。

为了计算MaxEdge(p, q),我们将p和q之间的路径分为两部分:从p到Lca(p, q),从Lca(p, q)到q。每个部分看起来都像是从顶点到其父级的路径,因此我们可以使用我们的Parent(v, i)和MaxParentEdge(v, i)函数来计算这些部分的MaxEdge。

代码语言:javascript
复制
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;
}

基本上,函数QuickMaxEdge(v, parent_v)做长度2^i的跳跃,以覆盖parent_v和v之间的距离。在跳转期间,它使用预先计算的MaxParentEdge(v, i)值来更新答案。

考虑到MaxParentEdge(v, i)和Parent(v, i)都是预先计算出来的,MaxEdge(p, q)工作在O(log|V|)中,这就导致了对初始问题的O(|E|log|V|)解决方案。我们只需要对不属于T的所有边进行迭代,并计算每个边的W(e) - MaxEdge(p, q)。

票数 3
EN

Stack Overflow用户

发布于 2014-03-01 23:29:25

设V为顶点集,E为边集。

让T是使用任何标准算法获得的MST。

设maxEdgeInPath(u,v)是T中从顶点u到顶点v的唯一路径上的最大边。

对于每个顶点u在T上执行BFS,这给出了属于V-u的所有x的maxEdgeInPath(u,x)。

找到一个边缘(x,y),它不属于最小化w(x,y) - w(maxEdgeInPath(x,y))的T

2 2ndMST的重量为W(T) + w(x,y) - maxEdgeInPath(x,y)

这是基于本链接中提供的算法。我不确定这是否正确,我希望有人能在这里添加一个证据。

完备性:计算一个顶点的BST时,在O(V+E) = O(V)中以E = V-1作为T,因此总的时间复杂度为O(V^2)。

票数 1
EN

Stack Overflow用户

发布于 2014-03-20 17:58:42

代码语言:javascript
复制
#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;
}
票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/22109647

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档