时间和空间复杂度

时间复杂度：

• 这里的边扫描版本的时间复杂度为 O(V * E)：进行 V-1 轮，每轮扫描全部 E 条边。使用二叉堆和邻接表时，Prim 的运行时间为 O((V + E) log V)。

空间复杂度：

• inTree 数组需要 O(V) 空间（输入边除外）。

总结：

• Prim 从一棵树开始扩展，每次都添加一条离开这棵树的最便宜的边，直到包含所有顶点。
• 它使用不同的策略，得到与 Kruskal 相同的最小总权重。