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

Question

博鲁夫卡算法(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

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