Kruskal 的 MST 算法的这段代码如何工作？

Question

下面是 Kruskal 算法 的 C++ 代码，用于查找我的导师给出的图的最小成本生成树。

我没看懂代码。我想确切地知道代码的哪一部分正在检查包含边缘的生长森林中循环的形成。

我也想知道 parent[] 数组的具体用途是什么。

此外，它是否比使用 DFS（深度优先搜索）检查循环更好？

代码如下：

#include<stdio.h>
#include<stdlib.h>

int i, j, k, a, b, u, v, n, ne = 1;
int min, mincost = 0, cost[9][9], parent[9];

int find(int);
int uni(int, int);

int main()
{
    printf("\n\tImplementation of Kruskal's algorithm\n");
    printf("\nEnter the no. of vertices:");
    scanf("%d",&n);
    printf("\nEnter the cost adjacency matrix:\n");

    for (i = 1; i <= n; i++)
    {
        for(j = 1; j <= n; j++)
        {
            scanf("%d",&cost[i][j]);
            if(cost[i][j] == 0)
                cost[i][j] = 999;
        }
    }

    printf("The edges of Minimum Cost Spanning Tree are\n");

    while(ne < n)
    {
        for(i = 1, min = 999; i <= n; i++)
        {
            for(j = 1; j <= n; j++)
            {
                if(cost[i][j] < min)
                {
                    min = cost[i][j];
                    a = u = i;
                    b = v = j;
                }
            }
        }
        u = find(u);
        v = find(v);
        if(uni(u,v))
        {
            printf("%d edge (%d, %d) =%d\n", ne++, a, b, min);
            mincost += min;
        }
        cost[a][b] = 999;
    }
    printf("\n\tMinimum cost = %d\n",mincost);
}

int find(int i)
{
    while(parent[i])
    i = parent[i];
    return i;
}

int uni(int i,int j)
{
    if(i!=j)
    {
        parent[j]=i;
        return 1;
    }
    return 0;
}

注：

我知道代码有点乱，如果用户输入的值超过 9，用户输入将导致失败，但我不想在没有的情况下专注于那部分了解它是如何工作的。我只知道它选择最小成本边，检查它是否形成循环，然后将其值设置为无穷大（这里 999）。我不知道它是如何以及在哪里检查循环形成的。请帮忙解释一下。

Answer 1

while 循环内的代码 main 找到尚未考虑的最轻边缘。该边缘位于节点 u 和 v 之间。只有当u和v已经属于同一棵树时，这条边才能形成环。

这个：

u=find(u);
v=find(v);

找到u和v所属树的根。然后 main 将这两个根传递给 uni:

if(uni(u,v))
  ...

int uni(int i,int j)
  {
    if(i!=j)
      {
        parent[j]=i;
        return 1;
      }
    return 0;
  }

如果两个根相同，则代码什么都不做，不使用边。

Answer 2

I want to know exactly what part of the code is checking for formation of a cycle in the growing forest of included edges. I also want to know that what exactly is the purpose of the parent[] array.

您似乎了解了 Kruskal 算法的大致思路，但对一些更重要的细节了解不多。特别是，我必须假设您不了解此算法中 "disjoint set"（a.k.a。"set union" 和其他名称）数据结构的核心和基本用途。因为如果您这样做了，您肯定会在您的代码中认识到，这就是 parent 数组所起的作用。即使您没有从名称中猜出，find() 和 uni() 函数也是一个绝妙的赠品。

该代码使用不相交的集合结构来跟踪到目前为止添加到图中的边连接了哪些顶点组。 find() 函数确定给定顶点属于哪个集合，如果两个顶点属于同一集合，则拒绝候选边。当两个子图通过接受边连接时，uni() 函数将两个集合合并为一个集合。

Also, is it a better way than checking for cycles using DFS (depth first search)?

性能细节在某种程度上取决于不相交集的实现。这里的一个特别简单，但更复杂的可以减少搜索的摊销成本，从而获得比使用 DFS 更好的算法整体性能。

Answer 3

好的。在继续解释之前，请花点时间阅读 this 在 HackerEarth 上关于 Kruskal 算法的精彩教程，以便您对要查找的内容有一个大致的了解。

现在关于算法：

注意：首先忽略前三行，只看main中的代码，假设所有变量都是事先声明的。

现在让我们开始吧：

printf("\n\tImplementation of Kruskal's algorithm\n");
printf("\nEnter the no. of vertices:");
scanf("%d",&n);
printf("\nEnter the cost adjacency matrix:\n");
for(i=1;i<=n;i++)
{
    for(j=1;j<=n;j++)
    {
        scanf("%d",&cost[i][j]);
        if(cost[i][j]==0)
            cost[i][j]=999;
    }
}

第一行要求顶点的数量和邻接矩阵以及每个顶点到任何其他顶点的成本。它也看起来像当没有任何边连接 2 个顶点时，成本设置为 999，这样当设置为 0 时它不会错误代码。

这是邻接矩阵的样子。

假设您的图表如下所示邻接矩阵如下：

   1  2  3
  _________
1| 0  0  11
2| 0  0  0
3| 11 6  0

意味着 1 连接到 3，成本为 11。2 没有连接到任何顶点，3 连接到 1，成本为 11，连接到 2，成本为 6。上面的代码会将上面的矩阵更改为：

   1    2    3
  _____________
1| 999  999  11
2| 999  999  999
3| 11   6    999

这样算法就不会选择 0 作为最低成本。并避免选择非连接顶点。

之后我们有：

printf("The edges of Minimum Cost Spanning Tree are\n");
while(ne < n)
{
    for(i=1,min=999;i<=n;i++)
    {
        for(j=1;j <= n;j++)
        {
            if(cost[i][j] < min)
            {
                min=cost[i][j];
                a=u=i;
                b=v=j;
            }
        }
    }
    u=find(u);
    v=find(v);
    if(uni(u,v))
    {
        printf("%d edge (%d,%d) =%d\n",ne++,a,b,min);
        mincost +=min;
    }
    cost[a][b]=999;
}
printf("\n\tMinimum cost = %d\n",mincost);

首先你要知道Kruskal算法是用连通分量来判断2个顶点是否连通（这也是kruskal算法不生成圆的原因）。那么让我们看看代码的作用。

for(i=1,min=999;i<=n;i++)
{
    for(j=1;j <= n;j++)
    {
        if(cost[i][j] < min)
        {
            min=cost[i][j];
            a=u=i;
            b=v=j;
        }
    }
}

这有点直截了当。它所做的是遍历矩阵并找到其中的最小值。所以对于我给出的例子，它会首先找到 6。所以min=6，u=3（起始顶点），v=2（结束顶点）。所以现在为了理解接下来会发生什么，你必须阅读关于不相交集和连通分量的内容。幸运的是，在 HackerEarth 上有一个 10 分钟的阅读教程，它将帮助您了解连接组件的工作原理。你可以找到它 here.

这就是正在发生的事情。该算法表示现在最小的成本是从 3->2，成本为 6。让我们将其添加到我们在后台使用连接组件构建的图形中，并将成本设置为 999，这样我们就不会重新考虑它。所以在这里：u=find(u);

它转到父数组并检查位置 3(arr[3]) 谁是父数组？答案是 3，因为我们还没有将它连接到任何其他组件。接下来它对 2(arr[2]) 做同样的事情，它也保持不变，因为我们没有连接它。其他任何事情。然后将它们统一为一个。即数组现在变为：

[1, 2, 3] -> [1, 3, 3] (minCost is now equal to 6)

然后它将 min 添加到 minCost，这就是答案。并将成本从 3->2 更改为 999，因此我们不会重新考虑它。

它重复这个过程，所以我们有：

    // min=6, u=3, v=2
    [1, 2, 3] -> [1, 3, 3] // minCost = 6
    // min=11, u=1, v=3
    [1, 3, 3] -> [1, 3, 1] // minCost = 17
    // min=11, u=3, v=1 !!! CAREFUL NOW
    Moving over to 
    parent of parent[3] == parent[1] meaning that they have the same parent so they are CONNECTED. 
    if(uni(u,v)) <-- This won't run since uni(3, 1) will return 0 meaning that they are connected so the min won't be added to minCost this time.

算法到此结束。它打印出 17 的最终成本，您就完成了。 ne 变量只是作为一个计数器，使打印更容易理解。

希望对您有所帮助。请务必阅读我链接的教程，它们将真正帮助您理解逻辑，因为美妙的 Kruskal 算法。

上述链接：

Kruskal 算法：https://www.hackerearth.com/practice/algorithms/graphs/minimum-spanning-tree/tutorial/

连通分量：https://www.hackerearth.com/practice/data-structures/disjoint-data-strutures/basics-of-disjoint-data-structures/tutorial/

Kruskal 的 MST 算法的这段代码如何工作？

How does this code for Kruskal's MST algorithm work?

c++

algorithm

minimum-spanning-tree

kruskals-algorithm