无向图和有向图的最小生成树算法有什么区别？

Question

无向图 MST 算法（Prim 或 Kruskal 的）是有向 MST 算法 (Edmond/Chiu) 的一般形式吗？定向案例的MST源码怎么这么难找？能否用无向解得到有向图中的MST？

这与以下内容有关： Why can't Prim's or Kruskal's algorithms be used on a directed graph?

Answer 1

您问题的核心似乎是找到 MST 的原因（技术上称为 最佳分支 或 最小成本树状结构）在有向图中与在无向图中找到 MST 不同，因此更难。

Prim 和 Kruskal 的算法都有效，因为 cut 属性。如果 G = (V, E) 是一个图，那么对于 G 中的任何割 (S, V - S)，如果有一条最小成本边 {u, v} 穿过该割，则该边必须属于所有 MST G. 不幸的是，这属性在定向情况下不是真的。这是一个反例：

      2
  A ----> B
  |      | ^
1 |  -99 | | 1
  |      v |
  +-----> C

在这里，以A为根的最小成本树状结构是这个：

然而，看看切割 ({A}, {B, C}) 穿过这个切割的成本最低的边是边 (A, C)，但这条边没有出现在任何最小-植根于 A 的成本树

如果没有切割属性，Prim 的算法和 Kruskal 的算法都会失败。在此处给出的图表上尝试运行 Prim 的算法，从节点 A 作为您包含的节点开始。您将添加边 (A, C)，然后添加边 (C, B)，给出次优的树状结构。现在，在这里尝试运行 Kruskal 的算法。您将首先添加边 (B, C)，然后添加边 (A, C)。不幸的是，这实际上不是树状结构，因为它没有根节点。

寻找最小成本树状结构的标准算法 (Edmonds-Chu) 实际上可能在精神上更接近 Boruvka's algorithm。 Boruvka 的算法的工作原理是同时为每个节点选择连接到该节点的成本最低的边，并将其添加到候选 MST。然后，您将以这种方式形成的所有 CC 收缩为单个节点并重复此过程，直到您拥有树。

在无向的情况下，只要边权重不同，该算法就永远不会引入循环（证明这一点是一个很好的练习），但在有向算法中情况并非如此。上面给出的图表是一个很好的例子——如果你尝试这样做，你从 A 中选择 (A, C)，从 C 中选择 (C, B)，从 B 中选择 (B, C)，形成循环 (B, C) , B). Edmonds-Chu 算法使用的校正方法是将这些循环之一收缩为单个节点，然后在缩减图中重复此过程并根据结果“取消收缩”循环。从这个意义上说，它类似于 Boruvka 的算法，但进行了适当的修改。

希望对您有所帮助！

Answer 2

我找到了一些不错的 slides，其中对差异进行了清晰明确的解释，并提供了清晰的图表和示例

无向图和有向图的最小生成树算法有什么区别？

What's the difference between the minimum spanning tree algorithm for undirected vs directed graphs?

algorithm

tree

graph

graph-algorithm