标签: kruskals-algorithm

我可以编写Prim和Kruskal的算法来找到C++或Java中的最小生成树,但我想知道如何在Haskell中使用O(mlogm)或O(mlogn)实现它们(纯函数式程序更好).非常感谢.

我们已经看到跨越树木和砍伐密切相关.这是另一种联系.让我们删除Kruskal算法添加到生成树的最后一个边缘; 这会将树分成两个部分,从而在图中定义一个切口(S,S).我们怎么说这个减产？假设我们正在使用的图是未加权的,并且其边缘是随机均匀排序的,以便Kruskal算法处理它们.这是一个值得注意的事实:概率至少为1/n ^ 2,(S,S)是图中的最小切割,其中切割的大小(S,S)是在S和S之间交叉的边数这意味着重复过程O(n ^ 2)次并输出最小的切割得到G的最小切割概率很高:O(mn ^ 2 log n)算法用于未加权的最小切割.一些进一步的调整给出了由David Karger发明的O(n ^ 2 log n)最小割算法,这是对这个重要问题最快的已知算法.

• 这是否取决于通过Kruskal算法处理图形的n ^ 2种独特方法的事实？我的意思是,如果Kruskal算法只有 3种独特的方法来处理具有10个节点的图形,重复该过程n ^ 2次将不会产生n ^ 2个唯一的"最后边缘".如果在最小切割次数少于n ^ 2的情况下(小于n ^ 2个唯一的"最后边缘"),它将如何工作？

• 如果总共少于n ^ 2个边缘怎么办？例如,您可以拥有10个节点的连接图,只有9个边,这意味着无论您重复算法多少次,您都不会有n ^ 2个唯一的"最后边".在这种情况下它会如何运作？

• 绕过每个边缘并检查边缘是否是最小切割不是更容易吗？在n个节点的图中,唯一边的最大数量是n + n-1 + n-2 ... + 1个边,小于n ^ 2.并且考虑到n ^ 2小于n ^ 2 log n,为什么不绕过所有边缘,因为这更快？

我正在尝试开发一种聚类算法,其任务是在一组2D点上找到k类(使用k作为输入),使用轻微修改的Kruskal算法来找到k个生成树而不是一个.

我使用兰特指数将我的输出与建议的最优值(1)进行了比较,对于k = 7,我得到了95.5%.比较可以在下面的链接中看到.

问题:

该组具有5个明显间隔的簇,这些簇很容易被算法分类,但是当k> 5时结果相当令人失望,这就是事情开始变得棘手的时候.我相信我的算法是正确的,也许数据对于Kruskal方法特别糟糕.已知单链接聚类聚类(例如Kruskal)在某些问题上表现不佳,因为它将聚类质量的评估减少到一对点之间的单一相似性.

算法的想法很简单:

• 使用数据集制作完整的图形,边缘的权重是该对之间的欧氏距离.
• 按重量对边缘列表进行排序.
• 对于每个边(按顺序),如果它不形成循环,则将其添加到生成林.遍历所有边缘或剩余森林有k棵树时停止.

底线: 为什么算法失败了？这是Kruskal的错吗？如果是这样,为什么呢？有什么建议可以在不放弃Kruskal的情况下改善结果？

(1):Gionis,A.,H.Mannila和P. Tsaparas,聚类聚合.ACM数据知识发现交易(TKDD),2007.1(1):p.1-30.

谁能解释为什么 Kruskal 产生的树与 Dijkstra 不同？

我知道 kruskal 处理边的非降序顺序，但 Dijkstra 利用了优先级队列，但仍然无法理解为什么它们的结果树不同？

我试图尽可能高效地实施Kruskal.

对于运行时效率,使用堆或排序算法对边进行排序是否有区别？

还有哪些其他技术可以使Kruskal算法更有效地工作？

MAKE-SET(x?
    x.p = x
    x.rank = 0

UNION(x, y)
     LINK(FIND-SET(x),FIND-SET(y))

LINK(x, y)
    if x.rank > y.rank
        y.p = x
    else 
        x.p = y
        if x.rand == y.rank
            y.rank = y.rank +1

The FIND-SET procedure with path compression is quite simple:
FIND-SET(x)
    if x != x.p
        x.p = FIND-SET(x.p)
    return x.p

您可以在《算法导论》第 3章第 21 章中找到伪代码。

这是具有秩和路径压缩的不相交集森林的伪代码。从伪代码中我们可以看出，每次union操作之前，我们都会先找到每个节点的集合号。在路径压缩的 FIND-SET 操作中，x 和 y 的高度将始终只有 2。因为在 FIND-SET 之后 xp 和 yp 都将指向集合的根。为什么仍然需要按等级联合？

Shihab Shahriar 解决了我的问题，他的回答令人印象深刻！

我正在研究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循环究竟做了什么？

编辑:以及 - 的必要性 …

任何人都可以想到一种方法来修改Kruskal算法的最小生成树,以便它必须包含一定的边(u,v)？

Prim 算法和 Kruskal 算法都生成最小生成树。根据 cut 属性，这些算法的树的总成本将是相同的，但是这两种算法是否有可能以相同的总成本给出不同的 MST，因为我们在面临多个选择时按字母顺序选择它. 例如，我们比较 max(source,dest)，对于边 A->B 和 B->C，我们比较 A 中的 A->B 和 B 中的 B->C。

谢谢

我正在从geeksforgeeks 文章中研究 Kruskal 的 MST 。给出的步骤是：

\n

1. 按权重非降序对所有边进行排序。

\n

2. 选择最小的边。检查是否与目前形成的生成树形成环。如果没有形成循环，则包括该边。否则，丢弃它。

\n

3. 重复步骤(2)，直到生成树中有(V-1)条边。

\n

我真的不觉得有必要使用不相交集。为了检查循环，我们可以将顶点存储在访问的数组中，并在选择边时将它们标记为 true。循环程序，如果我们发现一条边的两个顶点都在访问的数组中，我们就会忽略该边。

换句话说，我们可以\xe2\x80\x99t而不是存储不相交集的森林，而只存储一个位数组来指示哪些顶点在先前的步骤中已链接到另一条边？