python-3.x - 完整图中节点集的最小生成树

Question

我试图找到连接点的最小生成树，但要尊重网络的现有布局。我很难在 python 的工具 networkx 中制定网络来找到最小生成树。

我需要找到仅覆盖点的最小生成树，考虑到我有这些点的坐标，我可以找到连接它们的线的长度。

关于如何做到这一点的任何指示或想法？

标签： python-3.xnetworkx

Answer 1

您正在解决 NP-hard 的Steiner 树问题。networkx提供了一种近似算法来解决这个问题：networkx.algorithms.approximation.steinertree.steiner_tree。