C实现Kruskal的MST算法

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,它本身属于由...表示的组件2.请注意,这2是一个代表,因为它有条目0.

您可以将其可视化为图形:

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

你看,我们目前有3个组件分别由2,7和9表示.

如果我们现在想要添加一个新的边缘(6,7),我们必须"上升树",直到我们分别找到代表2和7.正如我们所见,代表不一样,我们加上优势.

现在是另一个例子:我们想要添加边缘(6, 5),所以我们"爬上树"并2在两种情况下找到代表.因此,我们不添加边缘.

"在树上爬行"是由你明确说明的线条完成的.