标签: minimum-spanning-tree

参考Ada中的Kruskal算法,我不知道从哪里开始.

在我实际编写程序之前,我正在考虑所有内容,但我很遗憾我应该使用什么数据结构以及如何表示所有内容.

我最初的想法是在邻接列表中表示完整的树,但是阅读维基百科的算法说明create a forest F (a set of trees), where each vertex in the graph is a separate tree并且我不确定如何实现它而不会很快变得非常混乱.

它接下来create a set S containing all the edges in the graph要说的是,但我不知道最好的方法是做什么.我在想记录的数组,具有to,from和weight,但我失去了对forest.

最后,我试图弄清楚我是如何知道边缘是否连接两棵树,但我不知道最好的方法是做什么.

我不想找到所有最小的生成树,但我想知道它们中有多少,这是我考虑的方法:

• 使用prim或kruskal算法找到一个最小生成树,然后找到所有生成树的权重,并在它等于最小生成树的权重时递增运行计数器.

我找不到任何方法来查找所有生成树的权重,并且生成树的数量可能非常大,因此此方法可能不适合该问题.由于最小生成树的数量是指数级的,因此将它们计算起来并不是一个好主意.

• 所有权重都是正数.
• 我们也可以假设图表中没有重量超过三次.
• 顶点数量将小于或等于40,000.
• 边数将小于或等于100,000.

图中只有一个最小生成树,顶点权重不同.我认为找到最小生成树数量的最佳方法必须是使用此属性的东西.

编辑:

我找到了解决这个问题的方法,但我不确定,为什么会这样.任何人都可以解释一下.

解决方案:找到最小生成树的长度的问题是众所周知的; 用于查找最小生成树的两个最简单的算法是Prim算法和Kruskal算法.在这两个中,Kruskal的算法按其权重的递增顺序处理边缘.然而,Kruskal算法需要考虑一个重要的关键点:当考虑按权重排序的边缘列表时,可以将边缘贪婪地添加到生成树中(只要它们不连接已经以某种方式连接的两个顶点) ).

现在考虑使用Kruskal算法的部分形成的生成树.我们插入了一些长度小于N的边,现在必须选择长度为N的几条边.算法表明如果可能的话,我们必须在任何长度大于N的边之前插入这些边.但是,我们可以以我们想要的任何顺序插入这些边.另请注意,无论我们插入哪个边缘,它都不会改变图形的连通性.(让我们考虑两个可能的图形,一个具有从顶点A到顶点B的边缘,一个没有边缘.第二个图形必须具有A和B作为相同连通分量的一部分;否则从A到B的边缘将被插入到一点.)

这两个事实共同意味着我们的答案将是使用Kruskal算法的方式数量的乘积来插入长度为K的边(对于K的每个可能值).由于任何长度最多有三个边缘,因此可以强制使用不同的情况,并且可以在每个步骤之后确定连接的组件,因为它们通常是正常的.

设G =(V,E)为加权,连通和无向图,并且令T为最小生成树.设e是不在E中的任何边(并且具有权重W(e)).证明或反驳:TU {e}是包含G'=(V,EU {e})的最小生成树的边集.

嗯,这对我来说听起来是对的,所以我决定证明这一点,但我每次都被卡住了......

例如,如果e是具有最小权重的新边缘,那么谁可以向我们保证T中的边缘不会以不良方式被选择,这将阻止我们在没有E中其他边缘的"帮助"的情况下获得新的最小权重 - T？

我将不胜感激任何帮助,在此先感谢.

我有Robert Sedgewick关于算法的书中的这个问题.

关键边缘.从图中删除会导致MST权重增加的MST边缘称为临界边缘.显示如何在时间上与E log E成比例地查找图中的所有关键边.注意:此问题假定边权重不一定是不同的(否则MST中的所有边都是关键的).

请建议一种解决此问题的算法.

我能想到的一种方法是及时的工作EV我的方法是运行kruskal的算法.

但是每当我们遇到在MST中插入的边创建一个循环并且该循环已经包含具有相同边权重的边时,那么已插入的边将不是临界边(否则所有其他MST边都是临界边) .

这个算法是否正确？如何扩展此算法以及时完成E log E.

背景:

我有一个小的(目前不到100个)但正在增长的正则表达式集合,我想优化确定给定文本字符串的过程我的集合中哪些RE与文本字符串匹配.

一些RE有一个排序关系 - 例如,如果我知道字符串$ t匹配/ windows/i,那么我也知道$ t匹配/windows.*2000/i.因此,当我对我的集合中的RE测试$ t时,我可以跳过测试/ windows/i,如果我已经针对/windows.*2000/i测试了$ t并找到了匹配(尽管如果/windows.*2000/i确实如此)不匹配当然我不能跳过对/ windows/i的测试.

请注意,我的集合中的所有RE都不是完全等效的(对于任何一对RE,至少有一个匹配一个的文本字符串与另一个不匹配).

战略:

我想构建一个有向图G,其中有一个节点用于我的集合中的每个RE,并且每对RE的有向边具有排序关系(A - > B表示"匹配A意味着与B匹配"),并找到一个图的节点的"最小生成集"(节点S的最小集合,使得G中的每个节点位于源自S的有向路径上).

简单的部分:

有很多免费的算法可用于定向非循环图.因此,一旦为我的RE集合构建了图形G(这是不同的,应该保证G是非循环的),我不希望找到一个合适的算法来寻找G的最小生成集.

在哪里我需要帮助:

我想找到一种有效的方法来查找我的集合中的RE之间的所有排序关系 - 也许还要确保集合中没有两个RE是等价的(我需要一种方法来自动验证这个,因为新的RE是添加).

因此,我的(基本上是随机的)网络搜索至少提出了一个合理的说法,即确定两个RE之间存在什么(如果有的话)排序关系的合理方法确实存在,但尚未发现任何完整算法的描述.

有没有人知道现有的实现(用于比较RE),这些实现是合理有效的,可免费获得的,并且(理想情况下)是用一种流行的脚本语言或C/C++实现的？

"因此,Prim算法的总时间为O(V lg V + E lg V)= O(E lg V),这与我们实施Kruskal算法的渐近相同."

来自http://serverbob.3x.ro/IA/DDU0137.html

但为什么O(V lg V + E lg V)= O(E lg V)？

是因为E至少是V-1？

我试图找到一种检测给定图G是否具有两个不同的最小生成树的有效方法.我也试图找到一种方法来检查它是否有3种不同的最小生成树.我现在的天真解决方案是运行Kruskal算法一次并找到最小生成树的总重量.稍后,从图中移除边缘并再次运行Kruskal算法,并检查新树的权重是否是原始最小生成树的权重,对于图中的每个边都是如此.运行时是O(| V || E | log | V |),这根本不是很好,我认为有更好的方法.

任何建议都会有所帮助,在此先感谢

我想知道Boruvkas算法和Kruskals算法之间的区别。

他们的共同点：

• 两者都在无向图中找到最小生成树（MST）
• 两者都将最短边添加到现有树中，直到找到 MST
• 两者都从整体上看待图，这与 Prims 算法不同， Prims算法将一个又一个节点添加到 MST 中
• 两种算法都是贪婪的

唯一的区别似乎是，Boruvka 的视角是每个单独的节点（从那里寻找最便宜的边），而不是查看整个图（像 Kruskal 那样）。

因此，Boruvka 似乎应该相对容易并行执行（与 Kruskal 不同）。真的吗？

给定两个相连的加权图和一组可以在两个图之间“过河”的顶点对，任务是找到由两个图组成的图的 MST（最小生成树），该图与交叉点相连接，其中包含N次过河。给定安排的解决方案总是存在的。

在下面的示例中，左侧图具有顶点 (0, 1, 2, 3)，右侧图具有顶点 (4, 5, 6, 7, 8)。将从 3-4、3-5、2-4、2-5 中选择边，并且 N = 2。恰好包含两个过河点的最小生成树用红色表示。

首先，根据MST的割性质，我认为要选择的交叉点是N个最低的交叉点。

其次，在尝试寻找 MST 时，如何强制 Primm 算法选择一些边？您不能只预先连接所选的交叉点，因为它可能只会选择一个。

首先，我的想法是对其进行修改，使其在此过程中始终选择选定的交叉点（上图中的 3-5 和 2-4），但这可能会创建一个循环，对吗？它必须以某种方式知道在强制选择某些顶点时不要创建循环。

我的第二个想法是找到左侧和右侧的 MST，然后才尝试连接它们 - 但这不会创建一个循环吗？如果您只是用最大值边打破循环会怎样？这不会自动产生答案吗？您可以确保双方都有自己的 MST，这些 MST 与最便宜的路径相连，并且不存在环路。

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