最小生成树的实现算法之普里姆算法（Prim）

算法定义

简单来说，普里姆算法从图中某个顶点开始，将其作为一棵树的根节点，然后这棵树会逐步长大，一直长大到覆盖图中的每一个顶点为止，每一步都会从剩下的与当前操作节点相邻的顶点中找到一条权重最小的边加入到树中，当算法终止时，这棵树就是一棵最小生成树。

下面是图示过程：

从 V1 开始，从与其相邻的顶点中找到权重最小的边，连接的是 V3，然后从 V3 开始，在于 V3 相邻的顶点中找到权重最小的边，连接的是 V6，再从 V6 开始，依次类推，当到达某个顶点，与该顶点相邻的所有顶点都已经访问过，则需要往前回溯，从所有前驱节点中找到权重最小的一条未添加的边开始，继续上述流程，直到所有顶点都已经覆盖，此时，通过 n-1 条边连接 n 个顶点构成的树就是最小生成树。

算法复杂度

对于顶点数为 n 的无向连通网，普里姆算法实现最小生成树对应的时间复杂度是 O(n2)（嵌套循环，舍弃低阶对边的遍历），还需要额外的空间存储顶点和边，对应的空间复杂度是 O(n+e)，其中，n 是顶点数，e 是边数。