C實現MST的Kruskal算法

Question

我正在研究Kruskal的算法，用於查找給定圖的MST，並且我理解基本概念，您必須首先將所有頂點視爲林。之後，您必須找到最小邊並將邊的頂點連接到一棵樹中。遞歸地做這件事，直到只剩下一棵包含所有頂點的樹。

我碰到了這個算法的以下實現。

#include<iostream.h> 

int p[10]; 

void kruskal(int w[10][10],int n) 
{ 
    int min,sum=0,ne=0,i,j,u,v,a,b; 
    for(i=1;i<=n;i++) 
    p[i]=0; 
    while(ne<n-1) 
    { 
     min=999; 
     for(i=1;i<=n;i++) 
     for(j=1;j<=n;j++) 
     { 
      if(w[i][j]<min) 
      { 
        min=w[i][j]; 
       u=a=i; 
       v=b=j; 
      } 
     } 
     while(p[u]) 
      u=p[u]; 
     while(p[v]) 
      v=p[v]; 
     if(u!=v) 
     { 
      ne++; 
      sum+=min; 
      cout<<"\nedge "<<a<<"-->"<<b<<" is "<<min; 
      p[v]=u; 
     } 
     w[a][b]=w[b][a]=999; 
    } 
    cout<<"\nmin cost spanning tree= "<<sum; 
} 

void main() 
{ 
    int w[10][10],n,i,j; 
    clrscr(); 
    cout<<"enter no.of vertices\n"; 
    cin>>n; 
    cout<<"enter weight matrix\n"; 
    for(i=1;i<=n;i++) 
     for(j=1;j<=n;j++) 
      cin>>w[i][j]; 
    for(i=1;i<=n;i++) 
     for(j=1;j<=n;j++) 
      if(w[i][j]==0) 
       w[i][j]=999; 
    kruskal(w,n); 
} 

什麼，我不明白的是，需要：

while(p[u]) 
    u=p[u]; 
while(p[v]) 
    v=p[v]; 

究竟是什麼這兩個while循環呢？

編輯：也有必要OF-

for(i=1;i<=n;i++) 
     for(j=1;j<=n;j++) 
      if(w[i][j]==0) 
       w[i][j]=999; 

Answer 1

Kruskals算法要加入一定優勢(a, b)。然而，在這之前，它必須檢查a和b是否已經連接（如果是的話，它不會添加邊緣）。

您的四條給定的行只是檢查是否已連接a和b。

要完全理解這一點，您必須瞭解以下內容：最初u和v分別設置爲a和b。陣列p存儲連接的組件。即p[x] = y表示：x位於y的連接組件中。請注意，最初每個頂點表示其自己的連接組件，由p[n1] = 0, p[n2] = 0, ...（即組件被設置爲0）指示。

此外，請注意，每個連接的組件由一個頂點表示。

所以，在這裏我們去：while(p[u])檢查u是否是組件的representant（u是當且僅當p[u] == 0一個representant，這將導致while循環停止）。因此，如果u是組件的代表，則停止。

更有趣的部分如下：如果u不是表示形式，則算法查找p[u]，即查找哪個節點是u的組成部分的表示形式。然後相應地更新u（u=p[u]）。

你可以認爲這整場比賽的圖表。考慮表示被連接的部件的下表：

u | 1 2 3 4 5 6 7 8 9 
p[u] | 2 0 2 3 2 1 0 9 0 

這意味着，節點1屬於由2表示組件。 4屬於由3表示部件，它本身屬於由2表示組件。請注意，2是一個代表，因爲它有條目0。

可以可視化此作爲一個圖：

2  7 9 
/|\  | 
1 3 5  8 
| | 
6 4 

你看，我們具有由2，分別爲7和9，表示目前3的組件。

如果我們現在想要添加一個新的邊緣(6,7)，我們必須「上樹」，直到分別找到表示者2和7。正如我們所看到的，代表們不一樣，我們添加邊緣。

現在再舉一個例子：我們要添加邊緣(6, 5)，所以我們「上樹」並在兩種情況下找到代表2。因此，我們不添加邊緣。

「走在樹上」是由你明確表示的路線完成的。