非平面图中是否存在最小生成树？我读过 prim 算法和三角不等式，我的图不满足三角不等式？
最佳答案
在正确性证明中我读到了 prim 的算法 here , 三角不等式一次都没有用过。所以 prim 的算法应该也适用于非度量图(那些不满足三角不等式的图)。因此，您可以应用 prim 的算法来查找连通加权无向图的 MST。
关于algorithm - 非平面图中是否存在最小生成树？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17022839/