我正在为此苦苦挣扎。更快的次优MST算法？
我们可以使用Kruskal算法或MST的Prim算法得到MST。
而对于 “次优” MST，我可以：
但这运行在O（VE），其中V是NUM顶点和E是边数。
如何使用联盟发现不相交集或LCA（最低共同祖先）获得加速？
提示，pseodo代码或web链接指针。
任何帮助，将不胜感激！谢谢:)
让V是顶点集，E是边集。
让T是使用任何标准算法获得的MST。
让maxEdgeInPath(u,v)为从顶点u到顶点v的唯一路径T上的最大边缘。
对于每个顶点u在T上执行BFS。这给出属于V-u的所有x的maxEdgeInPath（u，x）。
查找边缘(x,y)不属于T最小化w(x,y) - w(maxEdgeInPath(x,y))
重量2ndMST的是W(T) + w(x,y) - maxEdgeInPath(x,y)
这是基于在此link提供的算法。我不确定这是否正确，我希望有人在这里添加一个证明。
Compexity： 为了计算BST 1个顶点取O(V+E) = O(V)如E = V-1在T 因此总时间复杂度为O(V^2)
#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;
}
集Δ| T | =∞。
设置Enew = -1，Eold = -1。
对于不在树上的每条边e，请执行：
- 将边添加到树中，创建一个循环。
- 找到循环中的最大权重边，使得k！= e。
- 删除k
- 计算树权重δ=权重（e） - 权重（k）的变化。
- ifδ<Δ| T |那么Δ| T | =δ和Enew = e和Eold = k。
新树是从Enew取代Enew的结果。
运行时间正比于边缘
数量
参见此解决方案：http://web.mit.edu/6.263/www/quiz1-f05-sol.pdf
这需要增加另一个角度来看，加入的边缘后并计算所形成的循环中的最大加权边缘，从而找出新边缘和旧边缘之间的差异，我们需要保持引起差异的边缘的轨迹为m的最小值。该特定的边可以被添加以形成第二最佳的最小生成树。
虽然这个链接可能回答这个问题，但最好在这里包含答案的基本部分，并提供参考链接。如果链接页面更改，则仅链接答案可能会失效 – Marusyk
我将描述问题的多对数解法。我们来介绍一些定义。我们将表示：
V，由E设定图的边缘，并通过T设置MST边。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))是尽可能最小。这是可能的，以证明所述第二最佳MST可以通过从T除去MaxEdge(p, q)，然后加入到x = {p, q}T来构造。
现在我们来构建一个数据结构，它将能够在O(log|V|)中计算MaxEdge(p, q)。
我们为树T（它可以是任何顶点）选择一个根。我们将调用顶点v与根之间的简单路径中的边数 - 顶点的深度v，并将其表示为Depth(v)。我们可以通过depth first search计算O(|V|)中所有顶点的Depth(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的lowest common ancestor。有许多众所周知的数据结构允许在O(log|V|)甚至O(1)中计算Lca(v, u)查询（您可以在Wikipedia找到文章列表）。
为了计算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)。
如果你可以添加一个psedocode，它会更合适，人们可以很容易地理解你的答案。 – arunmoezhi
请你详细说明为什么这个工程？ – Math