标签: minimum-spanning-tree

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

可能重复:
所有最小生成树实现

如何以有效的方式在无向图中找到所有最小生成树？

所以我需要一些帮助来找到最小生成树的方法.假设我有一个邻接列表形式的图表:

A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35

第一个字母告诉您正在查看哪个节点,该数字表示与其他任何节点的连接数.例如,A有两个连接 - 一个连接到B和I.之后,字母后面的数字只表示边的权重.B的重量为12,我的重量为25.所以我原计划将这整个事物表示为一个名为String的数组Graph[8].每一行都是数组中的不同插槽.我无法通过Prims或Kruskalls算法找出如何实现这一目标.

我想制作一个动态最小生成树。我在 n 个顶点上有一个现有的 MS 树，我向这个新顶点的所有现有顶点添加了一个顶点和边。如何有效地更新新图的 MST？O(n) 将是最优的。我也可以使删除顶点操作有效吗？

我们已经看到跨越树木和砍伐密切相关.这是另一种联系.让我们删除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,为什么不绕过所有边缘,因为这更快？

可以通过运行 kruskal 算法找到最大生成树（只需更改边函数并首先考虑最大权重边）。我有兴趣找到最大权重欧几里得生成树。是否存在比 kruskal 更好的算法（更好的最坏情况运行时间）来找到这样的生成树？

我正在尝试开发一种聚类算法,其任务是在一组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.

给定加权的,连通的,简单的无向图G,每个边上的权重仅为1和2

我想以这种方式实现Prim的算法:

权重是1或2,所以我可以简单地将边缘存储在2个单独的列表中,一个用于权重为1的边缘,第二个用于权重为2的边缘.

要找到权重最小的边,我只需从第一个列表中取一个,除非它是空的,在这种情况下,我从第二个列表中取一个边.

访问和删除列表中的元素是O(1),因此Prim的算法将在O(V + E)中运行.

package il.ac.oranim.alg2016;

import edu.princeton.cs.algs4.*; 

public class MST12 {    
    private int weight; // weight of the tree
    private Edge[] mstEdges; // use this to store the edges of your Minimum Spanning Tree

    public MST12(EdgeWeightedGraph G, int s)  throws IndexOutOfBoundsException, DisconnectedGraphException, WrongWeightException {
        // check that the starting vertex is in the range 0,1,...,G.V()
        if (s < 0 || s >= G.V()) {
            throw new IndexOutOfBoundsException();
        }
        // check that the input graph …

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 解决了我的问题，他的回答令人印象深刻！

我有一个列表作为c4_leaves = [56,78,90,112]. 我正在尝试使用这些元素c4_leaves作为节点创建一个完整的图形。这是我尝试过的；

    V_ex = c4_leaves
    G_ex = nx.Graph() 
    G_ex.add_nodes_from(V_ex)
    G_ex = nx.complete_graph(4)


    for u,v in G_ex.edges():
        G_ex[u][v]['distance'] = distance(points33, u, v)

然后上图的最小生成树为：

 T_ex= nx.minimum_spanning_tree(G_ex, weight='distance')
 F_ex = list(T_ex.edges())

当我绘制时G_ex，它给了我正确的图形，但是当我打印最小生成树的详细信息时，它显示T_ex.nodes() = [0,1,2,3,56,78,90,112].

有人可以告诉我我正在做的错误吗？