图的最小生成树算法_如何从图得到最小生成树

生成树：一个连通图的生成树是指一个极小连通子图，含有图中的全部n个顶点，但只有足以构成一棵树的n-1条边。

构造网的一棵最小生成树，即：在e条带权的边中选取n-1条边，不构成回路，使“权值之和”最小。
最小生成树要解决的问题：

1. 尽可能选取权值小的边，但不能构成回路；
2. 选取n-1条恰当的边以连接网的n个顶点。

Prim算法（普里姆算法）

Prim算法思想

取图中任意一个顶点v作为生成树的根，之后往生成树上添加新的顶点w，注意添加的这个顶点要使该边的权值在所有连通顶点v和w之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有n个顶点为止。

一般情况下所添加的顶点应满足条件：
在生成树的构造过程中，图中n个顶点分属两个集合：已落在生成树上的顶点集U和尚未落在生成树上的顶点集V-U；则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。

看例子。首先，选择一个顶点a在生成树U中，

要保证权值最小，选e，d，c，b，然后选择g，

剩下的里面权值18,16,21，最小的,就是16了，所以选g。g和f之间27，d 和f之间21，最后选中f。

连通网用带权的邻接矩阵表示，并设置一个辅助数组closedge[]，数组元素下标对应当前V-U集中的顶点序号，元素值则记录该顶点和U集中相连接的代价最小（最近）边的顶点序号adjvex和权值lowcost。即对v∈V-U的每个顶点，closedge[v]记录所有与v邻接的、从U到V-U的那组边中的最小边的信息。

简单来说，就是先任取一点a作为生成树的根，选了就把1a的lowcost置