3359 blog.csdn.net/Luo shixian 099/article/details/51908175
关于图的一些概念定义：
连通图:在无向图中，如果任意两个顶点vivi和vjvj有路径相通，则将该无向图称为连通图。强连通图:在有向图中，当任意2个顶点vivi和vjvj有通路时，将该有向图称为强连通图。连通网:在连通图中，如果图的边具有一定的意义，则各边对应着被称为权的数； 权表示连接一个顶点的代价，这个连通图被称为连通网。生成树:连通图的生成树是指包含图中所有n个顶点的连通部分图，但只有足以构成一棵树的n-1条边。 具有n个顶点的生成树只有n-1条边。 如果在生成树中添加另一条边，它将始终成为一个循环。最小生成树连通网中所有生成树中，所有边的成本和最小的生成树称为最小生成树。
介绍两种最小生成树算法
1.Kruskal算法该算法可称为“加边法”，初始最小生成树边缘数为0，在每次迭代中选择满足条件的最小成本边缘，并将其添加到最小生成树边缘集合中。
1 .按成本从小到大排列图中所有边；
2 .将图中的n个顶点看作由独立的n棵树构成的森林
3 .从较小的权重起较大的方向选择边缘，在所选择的边缘所连接的两个顶点ui、viui、vi应属于不同的两个树的情况下，这两个树成为最小生成树的一个边缘，并将这两个树合并为一个树。
4 .重复(3)，直到所有顶点都在一棵树中，或者有n-1条边。
2.Prim算法该算法可称为“加分法”，在每次迭代中选择代价最小的边对应的点，添加到最小生成树中。 算法从某个顶点s开始，逐渐生长并覆盖整个连通网的所有顶点。
图所有顶点的集合为VV； 初始指令集u={s}，v=v头发的鸭子={s}，v=vu； 在可构成2个集合u、vu、v的边中，选择成本最小的边[u0，v0][u0，v0]，添加到最小生成树中，将v0v0编入集合u。 重复上述步骤，直到最小生成树中有n-1条边或n个顶点。 为了继续向集合u添加点，最小成本边必须同步更新； 必须创建一个辅助数组closedge以保存集合v的每个顶点和集合u的最小成本边信息。