图的最小生成树(图的最小生成树一定唯一)

连通图：在无向图中，每对顶点之间都有路径可达；

强连通图：在有向图中，每对顶点之间都有路径可达；

连通网：在有向图中，若连接两个顶点之间的边用一个数表示，这个数称为权，权具有特定的意义，代表这条边的代价；

生成树：一个连通图，它包含所有的n个顶点，且这个图中有n-1条边，一个生成树有且仅有n个顶点和n-1条边，若增加一条边，则构成环，若减少一条边，则不是连通图；

zui小生成树：在连通网的所有生成树中，权的和zui小的生成树。

Kruskal算法

初始zui小生成树边数为0，每次迭代找权zui小的边加入zui小生成树边的集合中，但不能形成环；

1. 将图中边按照权从小到大排序；
2. 从小到大选择边，且选择的边不构成环，则加入zui小生成树边的集合，若构成环，则继续选择下一条稍大且不构成环的边加入集合；
3. 重复2，直到集合中边的数目为n-1。

Prim算法

首先从权zui小的边开始，选择这条边的一个顶点加入zui小生成树顶点集合，一直到所有顶点都加入集合，且不构成环；

1. 设图中所有顶点集合为V，初始顶点集合u={s}，v=V-u；
2. 从u和v中找两个顶点u0和v0，两个顶点间边的权zui小，将v0加入集合u中；
3. 重复2，知道集合u的大小为n。

注：凡属于本公众号内容，未经允许不得私自转载，否则将依法追究侵权责任。

以上内容来源于网络，由“WiFi之家网”整理收藏！