克鲁斯卡尔最小生成树算法的C语言实现

Question

克鲁斯卡尔最小生成树算法的C语言实现

calgorithmgraph-algorithmkruskals-algorithm

4

我正在学习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;

- Chaitanya Nettem

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- phimuemue · Accepted Answer

Kruskal算法想要添加边，但在此之前，它必须检查和是否已连接（如果已连接，则不会添加该边）。
给出的四行代码正是检查和是否已连接。
要完全理解此操作，您需要知道以下内容：最初，和分别设置为和。数组
存储连接的组件，即表示：在的连接组件中。请注意，最初每个顶点代表自己的连接组件，由表示（即，将组件设置为0）。
此外，请注意，每个连接组件由一个顶点表示。
因此，我们继续：while(p[u])检查是否是组件的代表（如果是代表，则导致while循环停止）。因此，如果是组件的代表，它就会停止。
更有趣的部分是下面的内容：如果不是一个代表，该算法将查找，即查找哪个节点是的组件的代表。然后，相应地更新（=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

你看，我们当前有三个组件，分别由2、7和9表示。
现在如果我们想要添加一个新边(6,7)，我们需要"向上遍历树"，直到找到代表2和7的节点。如我们所见，这些节点不相同，因此我们添加了这条边。
再来看另一个例子：我们想要添加边(6,5)，那么我们就"向上遍历树"并在两种情况下找到了代表2。因此，我们不添加该边。
"向上遍历树"是通过你明确指定的行来完成的。