无向图MST算法（Prim或Kruskal）是有向MST算法（Edmond / Chiu）的一般形式吗？找到定向案例的MST源代码为何如此困难？我们可以使用无向解来获得有向图中的MST吗？
这与以下内容有关：为什么不能在有向图上使用Prim或Kruskal的算法？
您的问题的核心似乎是什么使在有向图中找到MST（技术上称为最佳分支或最小成本树状结构）与在无向图中找到MST相比变得不同，因此更难。
由于cut属性， Prim和Kruskal的算法都可以工作。如果G =（V，E）是图，则对于G中的任何切割（S，V-S），如果存在穿过该切割的成本最低的边{u，v}，则该边必须属于所有MST不幸的是，此属性在定向情况下不正确。这是一个反例：
2
A ----> B
| | ^
1 | -99 | | 1
| v |
+-----> C
在这里，以A为根的最小成本树状结构就是这个：
2
A ----> B
|
-99 |
v
C
但是，请查看切割（{A}，{B，C}）穿过此切割的成本最低的边缘是边缘（A，C），但该边缘不会出现在以A为根的任何最低成本的树状结构中。
没有cut属性，Prim算法和Kruskal算法都将失败。尝试在此处给定的图形上运行Prim算法，从节点A作为包含的节点开始。您将添加边（A，C），然后添加边（C，B），从而得到次优的树状度。现在，尝试在此处运行Kruskal算法。您首先要添加边（B，C），然后添加边（A，C）。不幸的是，这实际上不是树状结构，因为它没有根节点。
实际上，用于寻找最小成本树状发光的标准算法（Edmonds-Chu）实际上可能更接近Boruvka算法。Boruvka的算法的工作原理是为每个节点同时选择连接到该节点的成本最低的边，并将其添加到候选MST。然后，您可以将以此方式形成的所有CC压缩到单个节点中，并重复此过程，直到您拥有树为止。
在无方向情况下，只要边缘权重是不同的，该算法就永远不会引入循环（证明这一点是一个很好的练习），但是定向算法并非如此。上面给出的图形就是一个很好的例子-如果您尝试这样做，则从A中选择（A，C），从C中选择（C，B），从B中选择（B，C），形成循环（B，C ，B）。Edmonds-Chu算法使用的更正方法是通过将这些循环之一压缩到单个节点中，然后在精简图中重复此过程，并根据结果“解压缩”循环。从某种意义上讲，它与Boruvka的算法相似，但是进行了适当的修改。
希望这可以帮助！
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句