MST 的 Kruskal 算法的 C 实现

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 循环到底做什么？

编辑：还有必要性-

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 是否代表一个组件（u 是一个代表 iff p[u] == 0，这会导致 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表示的组件，而3本身又属于2表示的组件。请注意，2 是一个代表，因为它具有条目 0。

您可以将其可视化为图表：

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

您看，我们当前有 3 个组件，分别用 2、7 和 9 表示。

如果我们现在想要添加一条新边 (6,7)，我们必须“沿着树向上”，直到分别找到代表 2 和 7。正如我们所看到的，代表并不相同，我们添加了边缘。

现在另一个例子：我们想要添加边 (6, 5)，因此我们“沿着树向上”并在两种情况下找到代表 2。因此，我们不添加边缘。

“上树”是由你明确说出的台词完成的。