我正在爲此苦苦掙扎。更快的次優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