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。因此，我们不添加边缘。

“走在树上”是由你明确表示的路线完成的。