我在为这件事而挣扎。
对于MST,我们可以使用Kruskal算法或Prim算法得到MST。
对于“第二好”MST,我可以:
但这在O(VE)中运行,其中V是顶点的num,E是边的数。
如何使用Union-查找不相交集或LCA(最低公共连接程序)来加快速度?
提示、pseodo代码或web链接指针。
任何帮助都将不胜感激!谢谢:)
发布于 2015-10-14 00:23:53
我将描述这个问题的多对数解。让我们介绍一些定义。我们将表示:
V表示,图的边集由E表示,图的边集由T表示。v和u之间的图的边用{v, u}表示。e的权重W(e)法,MST的权重W(T)法。让我们考虑函数MaxEdge(v, u),它等于在v和u之间属于T的简单路径上具有最大权重的边。如果有几个边的最大重量,MaxEdge(v, u)可以等于它们中的任何一个。
要找到第二好的MST,我们需要找到这样的边缘x = {p, q},即:
x不属于T。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)
Parent(v, i),它等于顶点v的父级(可能是非直接父级)的顶点,深度等于Depth(v) - 2^i。MaxParentEdge(v, i),它等于MaxEdge(v, Parent(v, i))。这两种方法都可以用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];
}在我们准备好计算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。
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)。
发布于 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)。
发布于 2014-03-20 17:58:42
#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;
}https://stackoverflow.com/questions/22109647
复制相似问题