python - 有向图的 Boruvka 算法最小生成树

Question

Boruvka 算法（http://en.wikipedia.org/wiki/Bor%C5%AFvka's_algorithm）是否仅适用于无向图？

例如，如果我们有一个如下图结构：

node 1 -> node 2 (weight 1), node 3 (weight 1), node 4 (weight 1)

node 2 -> node 3 (weight 2)

node 3 -> node 4 (weight 2)

node 4 -> node 2 (weight 2)

那么最小生成树应该包括边：

1 -> 2

1 -> 3

1 -> 4

但是，Boruvka 的算法会吐槽

1 -> 2

2 -> 3

3 -> 4

因为，Boruvka 首先查看每个单独的节点，并将从该节点传出的最短边添加到 MST。

我知道在维基百科文章中它说边缘权重必须是不同的，但只要来自节点 1 的所有边缘权重都小于“外部”边缘权重（来自节点 2-4），那么它看起来像 Boruvka 的算法失败。这是因为它是有向图而不是无向图吗？

Answer 1

这是因为它是有向图而不是无向图吗？

是的。对于有向图，您必须考虑传入和传出边，然后算法将以相同的方式工作。最简单的方法是考虑底层的无向图。

Answer 2

您应该问自己的问题是“最小生成树”对于有向图意味着什么？您应该使用的算法取决于这个问题的答案。

Answer 3

最小生成树仅在无向图上定义，因此考虑到这一点您的问题没有意义。可能您正在寻找其他东西，例如，具有相同顶点集和最小边权总和的原始图的强连通诱导子图。在这种情况下，您不必获取树，实际上树也被定义为无向图。恕我直言，解决这个问题的算法将是计算上更难的问题。