连通图：在无向图中，每对顶点之间都有路径可达；
强连通图：在有向图中，每对顶点之间都有路径可达；
连通网：在有向图中，若连接两个顶点之间的边用一个数表示，这个数称为权，权具有特定的意义，代表这条边的代价；
生成树：一个连通图，它包含所有的n个顶点，且这个图中有n-1条边，一个生成树有且仅有n个顶点和n-1条边，若增加一条边，则构成环，若减少一条边，则不是连通图；
最小生成树：在连通网的所有生成树中，权的和最小的生成树。
Kruskal算法
初始最小生成树边数为0，每次迭代找权最小的边加入最小生成树边的集合中，但不能形成环；
- 将图中边按照权从小到大排序；
- 从小到大选择边，且选择的边不构成环，则加入最小生成树边的集合，若构成环，则继续选择下一条稍大且不构成环的边加入集合；
- 重复2，直到集合中边的数目为n-1。
Prim算法
首先从权最小的边开始，选择这条边的一个顶点加入最小生成树顶点集合，一直到所有顶点都加入集合，且不构成环；
- 设图中所有顶点集合为V，初始顶点集合u={s}，v=V-u；
- 从u和v中找两个顶点u0和v0，两个顶点间边的权最小，将v0加入集合u中；
- 重复2，知道集合u的大小为n。
注：凡属于本公众号内容，未经允许不得私自转载，否则将依法追究侵权责任。
以上内容来源于网络，由“WiFi之家网”整理收藏！
原创文章，作者：电脑教程，如若转载，请注明出处：https://www.224m.com/214057.html
