深圳做的好的电子行业招聘网站,汕头专业网站建设公司,wordpress邮箱注册功能,个人网站如何搭建一、定义
对于一个带权连通无向图G(V,E)#xff0c;生成树不同#xff0c;每棵树的权(即树中所有边上的权值之和)也可能不同。设R为G的所有生成树的集合#xff0c;若T为R中边的权值之和最小的生成树#xff0c;则T称为G的最小生成树(Minimum-Spanning-Tree, MST)。 二、手…一、定义
对于一个带权连通无向图G(V,E)生成树不同每棵树的权(即树中所有边上的权值之和)也可能不同。设R为G的所有生成树的集合若T为R中边的权值之和最小的生成树则T称为G的最小生成树(Minimum-Spanning-Tree, MST)。 二、手动实现算法
1Prim算法
介绍从某一个顶点开始构建生成树;每次将代价最小的新顶点纳入生成树直到所有顶点都纳入为止。
时间复杂度:O()适合用于边稠密图
例子1 1、我们从P城开始找到权最小的路径并构建出新的树。此时最小为1 2、再次寻找权最短的路径为P城到矿场。 3、如此反复得到最终结果。 2Kruskal算法
介绍每次选择一条权值最小的边使这条边的两头连通(原本已经连通的就不选)直到所有结点都连通。
时间复杂度:O(|E|*log2|E|)适合用于边稀疏图
例子2 1、我们从P城出发找一条权值最小的边我们找到学校到P城的路径为1最短于是连通它们。 2、再次找最短找到2连通它们。 3、反复执行这个操作直到所有的结点都连通。
