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

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