问题标签 [minimum-spanning-tree]

我如何描述一组具有 V 顶点和 E 边的图，其中确认 Prim 算法的优先级队列实现的最坏情况运行？

假设我有一个节点图（网络），权重如下： 1. 在两个节点之间的链接上单向行驶。2. 在两个节点之间的链接上以另一种方式行驶（这些可能不同）。3. 从一个链接更改为另一个链接。

此外，一些节点只是单向的。

在这种情况下，什么是最好的算法：a）找到最小生成树 b）找到两个节点之间的最短路径 c）找到“旅行推销员”路径（即，最短的路径去任何地方，重复最少） ?

另外，最好将双向事物视为两条单向路径，而不是在每个方向具有不同权重的双向路径？

- -一个例子 - -

其中 <2/3> 表示 2 左行和 3 右行的重量。^1/4 表示 1 上行和 4 下行。两个链接之间的单个数字是更改链接的成本 - 例如，从 AD 到 DF 成本为 8，从 AB 到 BE 成本为 2。

希望这是有道理的...

西蒙

（ps 为不好的术语道歉 - “链接”，“边缘” - 无论你喜欢什么;））

为了更好地解释权重类型，假设边缘是火车轨道，节点是车站。边缘的成本是火车在两个车站之间的行程时间，节点的成本是换乘时间的长短（即使在同一节点，边缘之间也可能有所不同，具体取决于站台的距离，服务的定期性等）。

I have a problem that I am really struggling with. I have a set of points with weighed edges and I need to create a minimum spanning tree to find the shortest amount of edges needed. I need to do it in java. Right now I have it creating an adjacency matrix and thats the point im stuck. I really have no idea where to go next. Any help would be awesome.

语境：

我有一个很小（目前不到 100 个）但不断增长的正则表达式集合，我想优化确定给定文本字符串的过程，以确定我的集合中哪些 RE 与文本字符串匹配。

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

请注意，我的集合中没有一个 RE 是完全等价的（对于任何一对 RE，至少有一个文本字符串与一个匹配而另一个不匹配）。

战略：

我想为我的集合中的每个 RE 构建一个有向图 G，并为每对具有排序关系的 RE 构建一个有向边（A -> B 表示“与 A 匹配意味着与 B 匹配”），并找到一个图的节点的“最小跨越集”（最小节点集 S 使得 G 中的每个节点都位于源自 S 的有向路径上）。

最简单的部分：

有许多免费可用的算法可用于处理有向无环图。因此，一旦为我的 RE 集合构建了图 G（不同的应该保证 G 是非循环的），我预计找到合适的算法来为 G 找到最小跨度集不会有太大困难。

我需要帮助的地方：

我想找到一种有效的方法来查找我的集合中的 RE 之间的所有排序关系——也许还可以确保集合中没有两个 RE 是等效的（我需要一种方法来自动验证这一点，因为新的 RE 是添加）。

因此，我的（基本上是随机的）网络搜索至少出现了一个合理的说法，即确实存在一种合理的方法来计算两个 RE 之间存在什么（如果有的话）排序关系，但还没有出现对完整算法的任何描述。

有谁知道现有的实现（用于比较 RE），它相当高效、免费提供，并且（理想情况下）用一种流行的脚本语言或 C/C++ 实现？

我为我的一个项目构建了一个邻接矩阵，我需要能够从该矩阵中构建一个最小生成树。通过阅读，Prim 的算法似乎最适合这种情况，但是我们不能假设该图是一个大的连接组件，因为我知道我们必须处理的至少一个图有大约几千个连接的组件。Prim 的算法在这里仍然可行吗？如果可行，我还需要做些什么吗？

我在这里用Java编码，我可以很好地构造邻接矩阵，只是我卡在这部分。

我尝试浏览图表并将某个 ID 的每个实例更改为更新的 ID，但它仍然导致了一个循环。解决非循环解决方案的计划是什么？

MST (Minimum Spanning Tree)添加新节点或改变路径距离后我们如何找到？

我需要帮助来解决这个问题。有谁能够帮助我？

谢谢。

“因此，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 吗？

我在 C 中工作，使用 igraph 库。我需要在 igraph_graph_t 类型（g）中获取给定图形存储的最小生成树。我还有一个 igraph_vector 包含每条边的权重（w）。以下是我的电话：

如何获得 mst 图中每条边的权重？我所需要的只是 mst 的成本。

谢谢，吉列尔莫。

我正在使用 igraph 库在 C 中工作。

我需要使用以下调用计算图的最小生成树：

在哪里：

• input_graph：要处理的图。是igraph_t类型。
• mst_tree：函数返回的 mst 树。是igraph_t类型。
• w： input_graph图每条边的权重向量。是igraph_vector_t类型。

按照 igraph 库中的要求，边和权重之间的关联由它们的索引给出，即 input_graph中的第一条边的权重由w向量的第一个元素给出，第二条边的权重由下式给出w向量的第二个元素，以此类推。

由于 mst_tree 的边是input_graph边 的子集 （因此， input_graph 和 mst_tree 中的边数量不同），因此无法通过关联它们的索引来获得mst_tree的边权重。

有一些 igraph 函数可以获取 mst_tree 中每条边的权重，只知道mst_tree、input_graph和 w？

吉列尔莫。