3. 最小生成树算法
"图的基本概念"中，我们总结了无向图之连通图，有向图之强连通图概念，下面补充一些概念
- 连通网：在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。
- 生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。
- 最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。
最小生成树集合表示
在一给定的无向连通图G = (V, E)中，(u, v) 代表连接顶点 u 与顶点v 的边，w(u, v) 代表此边的权重；若存在 T 为 E 的子集，G' = (V , T)构成的图为G的生成树，使得的 ∑w(T) 最小，则此 T 为 G 的最小生成树。
最小生成树其实是最小权重生成树的简称。
大白话：
在n个城市中建立一个通信网络，则连通这n个城市需要布置n-1一条通信线路，考虑如何在成本最低的情况下建立这个通信网？
于是可以引入连通图来解决上述问题，n个城市就是图上的n个顶点，然后，边表示两个城市的通信线路，每条边上的权重就是搭建这条线路所需要的成本，所以现在有n个顶点的连通网可以建立不同的生成树，每一颗生成树都可以作为一个通信网，当我们构造这个连通网所花的成本最小时，搭建该连通网的生成树，就称为最小生成树。
连通图&最小生成树
构造最小生成树算法大多采用了以下性质：
G＝ （V，E）为一个带权连通无向图，U是顶点集V的一个非空子集，若（u，v）是一条具有最小权的边，其中u∈U，v∈V-U，则必存在一棵包含边（u，v）的最小生成树。
两种最常见的最小生成树算法 --- 求带权连通无向图G＝ （V，E）的最小生成树G'
1. Prim算法（普里姆算法）
算法过程： 带权连通无向图G＝ （V，E）
-
初始化
顶点集 V' = {u0}，u0为图G中任一顶点，边集 E' = ∅
V - V' = {... ...}，E -
{（u , v）| u∈V'，v∈V - V'}，（u，v）∈E且（u，v）权值最小，将v加入到V'中，（u，v）加到E'中 - 循环步骤2，直至
V' = V
图解：
Prime算法
图解过程描述：
首先从图G的任一顶点a开始，将a加入V'集合，然后，寻找从与a有关联的边中，权重最小的那条边并且该边的终点b在顶点集合：（V-V'）中，我们也把b加入到集合V'中，并且输出边（a，b）的信息，这样我们的集合V'就有：{a,b}，然后，我们寻找与a关联和b关联的边中，权重最小的那条边并且该边的终点在集合：（V-V'）中，我们把c加入到集合V'中，并且输出对应的那条边的信息，这样我们的集合V就有：{a,b,c}这三个元素了，一次类推，直到所有顶点都加入到了集合V'。总结：不断加点的过程，称之为
加点法
代码实现
Code
2. Kruskal算法（克鲁斯卡尔算法）
算法过程： 带权连通无向图G＝ （V，E），Kruskal是按权值递增顺序选择合适的边来构造最小生成树的方法
-
初始化 ：
V'=V ， E'= ∅，T此时是一个仅含有|V|个顶点的森林（即初始化的T是图G将所有的边去掉构成的森林） -
循环 ：按图
G的边的权值递增顺序，依次从E-E'中选择一条边加入到T中，保证这条边加入T中不会构成回路，将这条边加入E'中，否则丢弃。循环，直到E'中含有一条n-1条边（即T构成为一棵树）
图解：仍以上图的连通网为例
Kruskal算法
图解过程描述：
（1）将图中的所有边都去掉（边集E'为空）。
（2）将边按权值从小到大的顺序添加到图中，保证添加的过程中不会形成环
（3）重复上一步直到连接所有顶点，此时就生成了最小生成树。这是一种贪心策略。总结：不断加边的过程，称之为
加边法
代码实现
Code
关键字：
最小生成树
Prim算法
Kruskal算法
