问题标签 [minimum-spanning-tree]

我正在编写一个算法来找到锦标赛图的主导集。有向图的最小生成树是否等价于图的支配集？换句话说，如果我找到锦标赛图的最小 MST（通过遍历所有顶点），那么我可以说这相当于图的主导集吗？

我已将问题简化为在图中找到最小生成树。但我想再有一个约束，即每个顶点的总度数不应超过某个常数因子。如何建模我的问题？MST是错误的路径吗？你知道任何可以帮助我的算法吗？

还有一个问题：我的图有重复的边权重，所以有没有办法计算唯一 MST 的数量？有没有算法可以做到这一点？

谢谢你。

编辑：按度数，我的意思是连接顶点的边的总数。重复边权重是指两条边具有相同的权重。

我想知道什么时候应该使用Prim 的算法，什么时候使用Kruskal 的算法来找到最小生成树？它们都有简单的逻辑，相同的最坏情况，唯一的区别是实现可能涉及一些不同的数据结构。那么决定因素是什么？

我已经在 C (www.bubbllellicious.es/prim.tar.gz) 中实现了Prim 的算法，但我只是想知道如何将其转换为Kruskal 的算法。

看起来它们非常相似，但我无法想象如何将旧代码修改为新代码。给点建议什么的就好了。我知道这很容易，但我仍然是 C 编程的 n00b ......

我有两组Animal对象。动物之间的距离是使用一种特定的算法来定义的，该算法着眼于它们的特征。我正在尝试设计一种方法来从两组（每个一组）中找到最小化距离的对。

我有一个想法：创建一个参数化Tuple类来配对Animals. PriorityQueue使用比较器创建一个以Tuple<Animal>根据两个成员之间的距离进行排序。然后，从PriorityQueue.

这是好的设计，还是浪费？我相信它会在 O(m+n) 时间内运行，其中 m 和 n 是每个集合的大小。

如果Tuple是一个参数化类，那么在其上使用仅适用于的 Comparator 将如何工作Animal？

我想使用这种findMinimalPair方法来创建一个生成树，以最小化Animal对象图的距离。如果我通过不断地从 中弹出对来做到这一点PriorityQueue，检查以确保每对仍然包含每个集合的一个成员，该怎么办？

这是一个基本的例子。以下是距离：

假设集合是：

A0

A1、A2、A3

这是元组的排序顺序，按距离：

所以我们看到 A3 是最接近的。然后将 A3 移动到第一个集合中：

A0, A3

A1, A2

再次，我们检查最小对：

现在A2被拿走了。看看它怎么运作？

这就是我最终做的。注释？

我编写了一个使用 Prim 方法解决 MST 的代码。我读到这种实现（使用优先级队列）应该有 O(E + VlogV) = O(VlogV) 其中 E 是边数和 V 边数但是当我查看我的代码时它根本不那样。如果有人能为我解决这个问题，我将不胜感激。

对我来说，运行时间似乎是这样的：

while 循环需要 O(E) 次（直到我们遍历所有边） 在该循环中，我们从 Q 中提取一个元素，这需要 O(logE) 时间。第二个内部循环需要 O(V) 时间（尽管我们不是每次都运行这个循环，很明显它会运行 V 次，因为我们必须添加所有顶点）

我的结论是运行时间为：O( E(logE+V) ) = O( E*V )。

这是我的代码：

I have a problem that can essentially be viewed as a graph. I'm considering using JGraphT to implement it instead of rolling my own. What would be the best way to get a minimum spanning tree out of a graph using JGraphT?

JGraphT有一个很好的斐波那契堆类。如何使用它来实现Prim 的最小生成树算法？

我正在尝试用 JGraphT 实现 Prim 的最小生成树算法。它看起来怎么样？

我遇到的一个问题是 JGraphT 对所有事情的处理方式都像它所指示的那样。所以有时有必要做出一些尴尬的调用来逆转g.getEdgeSource(e)，g.getEdgeTarget(e)如果他们没有碰巧是正确的。

我最初尝试使用 JGraphT 的 Fibonacci Heap 来实现这一点，但它太难了，所以我只是做了一个常规的 PQ。

我没有将不存在的边的权重设置为无穷大，而是没有将其添加到队列中。

建议？风格问题？明显的低效率？我应该使用的代码而不是我自己的代码？

我直观地觉得，如果使用 Prim 的算法来查找图的最小生成树，那么选择哪个根节点都没有关系 - 生成的 MST 无论如何都会具有相同的权重。这个对吗？