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

Is this because it is a directed graph not undirected?

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