图的最小生成树Prim算法

什么是最小生成树

最小生成树按通俗点来说就是图的一个子图，但不同的是这个图包含有原图的全部节点，但边的权值之和就尽量小

如果是非带权图那么他只有生成树并没有最小生树，如图

但最小生成树应该是这样子的

包含全部顶点但边的权值最小

不管是生成树还是最小生成树都不允许图中有环路 ！ ！ ！

普里姆算法-prim算法

Prim算法就是图的最小生成树算法之一，Prim 算法是一种求解加权无向连通图的 MST 问题的贪心算法。它能找出一个边的子集，使得其构成的树包含图中所有顶点，且边的权值之和最小。

Prim算法以图的顶点为基础，从首个初始顶点，寻找到达其他顶点权值最小的边，并把该顶点加入到“已到达顶点”的集合中，此时，这个集合就是这个图的最小生成树

prim算法的使用要点：

• 使用一个一维数组记录节点
• 节点上的值是是父节点的序号，而下标的值是代表这个节点的序号
• 第一个节点总是作为根节点（即序号为0的节点），因为没有父节点其值为-1

如有下图那么一个图

首先根节点进入数组，其值为-1

此时从根节点出发寻找权值最小的边，及其到达的节点，发现和节点2的边的权值更小，将其加入数组中,因为其父节点是根节点，所以值是根节点的下标，值为自己的序号

在从数组中已经加入的所有节点出发发现2和4的节点的边的权值最小

以此循环往复

此时全部顶点已经进入数组，数组就是这个图的最小生成树