algorithm - 非平面图中是否存在最小生成树？

Question

非平面图中是否存在最小生成树？我已阅读有关 prim 算法和三角不等式的信息，但我的图表不满足三角不等式？

Answer 1

在我在这里读到的 prim 算法的正确性证明中，没有使用过一次三角不等式。所以 prim 的算法也应该对非度量图（那些不满足三角不等式的图）有效。因此，您可以应用 prim 算法来找到连通加权无向图的 MST。