我正在为此苦苦挣扎。
我们可以使用Kruskal算法或Prim算法来获取MST。
对于"次优" MST，我可以：
但这需要O(VE)的运行时间，其中V是顶点数，E是边数。
如何利用并查集(disjoint set)或LCA(最近公共祖先)来加速？
提示，伪代码或网页链接指针。
任何帮助都将不胜感激！谢谢：）
我将描述该问题的多对数解决方案。让我们引入一些定义。我们用V表示图的顶点集，用E表示图的边集，用T表示最小生成树边集。
V，图的边集为E，最小生成树边集为T。v和u之间的边为{v, u}。e的权值为W(e)，最小生成树的权值为W(T)。让我们考虑函数MaxEdge(v, u)，它等于在从v到u的简单路径上属于T的边中具有最大权重的边。如果有几条最大权重的边，则MaxEdge(v, u)可以等于其中任何一条。
要找到第二好的最小生成树，我们需要找到这样的边x = {p, q}，满足：
x 不属于 T。W(x) - W(MaxEdge(p, q)) 最小。可以证明，次优最小生成树可以通过从 T 中删除 MaxEdge(p, q)，然后将 x = {p, q} 添加到 T 中来构建。
现在让我们构建一个数据结构，能够以 O(log|V|) 的时间计算 MaxEdge(p, q)。
我们为树 T 选择一个根节点（可以是任何顶点）。我们称顶点 v 到根之间的简单路径上的边数为顶点 v 的深度，并将其表示为 Depth(v)。我们可以通过 深度优先搜索 在 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的最近公共祖先。 有很多众所周知的数据结构可以在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。请注意保留 html 标签。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)即可。设V为顶点集合，E为边集合。
使用任何标准算法得到的最小生成树为T。
设maxEdgeInPath(u,v)为T中从顶点u到顶点v的唯一路径上的最大边。
对于每个顶点u在T上执行BFS。这给出了所有属于V-u的x的maxEdgeInPath(u,x)。
找到一条不属于T的边(x,y)，使得w(x,y) - w(maxEdgeInPath(x,y))最小。
第二小生成树的权重为W(T) + w(x,y) - maxEdgeInPath(x,y)。
这基于link中提供的算法。我不确定是否正确，希望有人能在这里添加一个证明。
复杂度：
计算1个顶点的BST需要O(V+E) = O(V)，因为在T中E = V-1
因此总时间复杂度为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;
}
参考此解决方案：http://web.mit.edu/6.263/www/quiz1-f05-sol.pdf
在添加边并计算形成的循环中的最大加权边后，需要添加另一个点，并因此找到新边和旧边之间的差异，我们需要跟踪导致差异最小的边。该特定边可以添加以形成第二个最佳最小生成树。
设 ∆|T| = ∞。
设置 Enew = -1 和 Eold = -1。
对于不在树上的每条边 e，执行以下操作：
- 将该边添加到树中，形成一个环。
- 找到环中最大权重的边 k，使得 k != e。
- 移除 k。
- 计算树权重的变化量 δ = weight(e) - weight(k)。
- 如果 δ < ∆|T|，则 ∆|T| = δ，Enew = e，Eold = k。
新树是通过用 Enew 替换 Eold 得到的。
运行时间与边数成比例。