java - 最小跨度树形jgraphx

Question

JGraphX 中是否有任何方法可以返回有向图的最小跨度树状结构？

我一直在使用 getMinimumSpanningTree 方法，将“directed”参数设置为“true”，但它实际上是 Prim 的算法，在某些有向图上失败。

Answer 1

据我所知，JGraphX 的功能集相当有限。您可以使用 Mathematica 和名为FindSpanningTree的函数来解决这个问题。默认情况下，它会为您选择最合适的功能，但如果您愿意，您可以将方法设置为MinimumCostArborescence。

要找到最小生成树，您有 3 个选项：

• 普里姆
• 克鲁斯卡尔
• 最小跨度树状

就我个人而言，我更喜欢 Kruskal 算法来处理大多数图表。

如果您认为设置JLink以使用 Mathematica 有点矫枉过正或想要一个免费的解决方案，那么可行的免费开源替代方案将是 Python 库Sage。Sage在通用图下具有称为edge_disjoint_spanning_trees的方法。

如果您更喜欢这个选项，那么这里有 5 种从 java 调用 python 的方法：link。