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

非平面图中有最小生成树吗？我读过prim算法和三角不等式，我的图不满足三角不等式？

最佳答案

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