Prim算法与断续图

Question

考虑到我们试图将prim算法应用于不连通图上。考虑这个不连通图有顶点a，b，c和d，其中这个顶点d是不连通的。现在我需要检查我的理解，如果我们在这个不连通图上应用prim算法，算法不会到达顶点d，因此只返回a，b和c点的MST。那么，这个假设是对的吗？

Answer 1

虽然MST的实际定义确实适用于连通图，但您也可以说，对于断开连接的图，最小生成林是由每个连通组件的最小生成树组成的。

这个问题增加了一个初始步骤来隔离每个连通子图，并将Prim的算法应用于每一个子图。

Answer 2

在不连通图上应用最小生成树是没有意义的，因为根据定义，它是不连通的，并且它不会跨越所有顶点。根据定义，它只与连通图相关：

最小生成树或最小权生成树是连通的(边加权无向图)的一个子集，它将所有顶点连接在一起，没有任何圈，并且具有最小的可能的总边权。