深圳鲜花团购网站建设,搜索seo优化托管,在word环境下wordpress,成都网销网站一.复习#xff1a;
1.生成树#xff1a; 对于一个连通的无向图#xff0c;假设图中有n个顶点#xff0c;如果能找到一个符合以下要求的子图#xff1a;
子图中包含图中所有的顶点#xff0c;同时各个顶点保持连通#xff0c;
而且子图的边的数量只有n-1条#xff0… 一.复习
1.生成树 对于一个连通的无向图假设图中有n个顶点如果能找到一个符合以下要求的子图
子图中包含图中所有的顶点同时各个顶点保持连通
而且子图的边的数量只有n-1条
那么这样的子图就是生成树一个连通图可能有多个生成树。
2.广度优先生成树 3.深度优先生成树 二.最小生成树最小代价树生成树必须包含图中所有的顶点
1.前言 假设有一个城市叫P城P城周围规划了学校、农场、电站、渔村、矿场
各个地方之间有上图所示的修路方案其中数字表示修路的成本比如修一条P城和学校之间的路需要1块钱修一条学校和矿场之间的路需要5块钱
现在为了节省P城的财政支出没有必要把所有的可行的道路都修一遍
因此需要制定一个修路方案这个方案要求所有地方都是连通的即各个地方之间是相互可到达的各个地方之间不一定是相邻的但是成本又必须降到最低此时有如下两种方案 左边的方案可以使得各个地方连通代价是20块钱图片打错了
右边的方案也可以使各个地方连通但代价是16块钱
但是否有更便宜的方案呢这就是最小生成树最小代价树要研究的问题。
对于带权的连通图它可以有多个生成树我们要从所有的生成树当中找出各个边的权值之和最小即代价最小的那棵树这个树就是最小生成树。
2.概念
注最小生成树研究的是带权的连通无向图。 3.特例当带权连通的无向图的权值都为一个数 以上述图片的带权连通无向图为例可得出如下两个生成树 由生成树的概念可知这两棵生成树的边都是5条边等于顶点总数减一此时有6个顶点由于每一条边的权值都为1因此这两棵生成树所有边的权值之和都为5
由此可知本例中带权无向图的任意一棵生成树的所有边的权值之和都为5因此最小的权值之和为5
结论假设一个带权连通无向图的顶点数为V个边为E条边的权值都为a
该图的所有生成树都只有(V-1)条边其权值之和为(V-1) * a由此可知最小生成树的权值之和为(V-1) * a因为所有树都一样。
4.性质 如果一个连通图本身就是一棵树树不存在环路也就是图中各个顶点连通但不存在环那么这个图的最小生成树就是它本身-因为如果连通图是树时那么它已经是生成树了而且无法再有更小的生成树了再有的话就会缺顶点不符合生成树的条件所以此时这个图的最小生成树就是它本身 只有连通图才有生成树 对于非连通图只会有生成森林因为非连通图不止一个连通分量生成的也就不止一个生成树最终就是生成森林这里生成必须要包括图中的所有顶点不然不符合生成的条件 5.总结 三.求最小生成树-Prim算法(普里姆算法)
1.例一 以上述图片为例挑选图中任意一个顶点从该顶点出发构建生成树 如上图比如从P城这个顶点出发构建生成树之后每次将代价最小的新顶点纳入生成树直到所有顶点都纳入为止
此时要构建的生成树中只有P城这一个顶点从P城出发分别对比到达学校、矿场、渔村、电站、农场所需要的代价可知从P城到达学校的代价最小因此接下来要把学校这个顶点纳入生成树如下图 如上图在当前生成树下重复刚才的步骤此时的生成树中有P城和学校两个顶点
现在要从P城或学校出发在农场、电站、渔村、矿场中选择一个代价最小的顶点连到当前生成树中
由上图可知最小的代价为4如下图 意味着可以把矿场或者渔村纳入生成树中
此时先把矿场纳入生成树如下图 如上图在当前生成树下重复刚才的步骤此时的生成树中包括P城、学校和矿场
现在要从P城或学校或矿场出发在农场、电站、渔村中选择一个代价最小的顶点连到当前生成树中
由上图可知最小的代价为2如下图 意味着把渔村纳入生成树中如下图 如上图在当前生成树下重复刚才的步骤此时的生成树中包括P城、学校、矿场和渔村
现在要从P城或学校或矿场或渔村出发在农场、电站中选择一个代价最小的顶点连到当前生成树中
由上图可知最小的代价为5如下图 意味着把农场纳入生成树中如下图 如上图在当前生成树下重复刚才的步骤此时的生成树中包括P城、学校、矿场、渔村和农场
现在要从P城或学校或矿场或渔村或农场出发在电站中选择一个代价最小的顶点连到当前生成树中
由上图可知最小的代价为3如下图 意味着把电站纳入生成树中如下图 如下图最终得到了最小生成树 也就是说按照如上图所得出的最小生成树进行施工的话只需要付15块钱也是最小代价。
2.例二 以上述图片为例挑选图中任意一个顶点从该顶点出发构建生成树 如上图比如从P城这个顶点出发构建生成树之后每次将代价最小的新顶点纳入生成树直到所有顶点都纳入为止
此时要构建的生成树中只有P城这一个顶点从P城出发分别对比到达学校、矿场、渔村、电站、农场所需要的代价可知从P城到达学校的代价最小因此接下来要把学校这个顶点纳入生成树如下图 如上图在当前生成树下重复刚才的步骤此时的生成树中有P城和学校两个顶点
现在要从P城或学校出发在农场、电站、渔村、矿场中选择一个代价最小的顶点连到当前生成树中
由上图可知最小的代价为4如下图 意味着可以把矿场或者渔村纳入生成树中
此时把渔村纳入生成树如下图 如上图在当前生成树下重复刚才的步骤此时的生成树中包括P城、学校、渔村
现在要从P城或学校或渔村出发在农场、电站、矿场中选择一个代价最小的顶点连到当前生成树中
由上图可知最小的代价为2如下图 意味着把矿场纳入生成树中如下图 如上图在当前生成树下重复刚才的步骤此时的生成树中包括P城、学校、渔村、矿场
现在要从P城或学校或渔村或矿场出发在农场、电站中选择一个代价最小的顶点连到当前生成树中
由上图可知最小的代价为5如下图 意味着把农场纳入生成树中如下图 如上图在当前生成树下重复刚才的步骤此时的生成树中包括P城、学校、渔村、矿场、农场
现在要从P城或学校或渔村或矿场或农场出发在电站中选择一个代价最小的顶点连到当前生成树中
由上图可知最小的代价为3如下图 意味着把电站纳入生成树中如下图 如下图最终得到了最小生成树 也就是说按照如上图所得出的最小生成树进行施工的话只需要付15块钱也是最小代价。
3.对比例一与例二分别得出的最小生成树 以上两棵生成树的最小代价都是15
因此同一个图可能有多个最小生成树虽然形态不同但是这些最小生成树的所有边的权值之和都是一样且最小的。
4.例三 以上述图片为例挑选图中任意一个顶点从该顶点出发构建生成树 如上图比如从农场这个顶点出发构建生成树之后每次将代价最小的新顶点纳入生成树直到所有顶点都纳入为止
此时要构建的生成树中只有农场这一个顶点从农场出发分别对比到达学校、电站、渔村、矿场、P城所需要的代价可知从农场到达电站的代价最小因此接下来要把电站这个顶点纳入生成树如下图 如上图在当前生成树下重复刚才的步骤此时的生成树中有农场和电站两个顶点
现在要从农场或电站出发在渔村、矿场、学校、P城中选择一个代价最小的顶点连到当前生成树中
由上图可知最小的代价为5如下图因此要把P城纳入生成树中 如上图在当前生成树下重复刚才的步骤此时的生成树中有农场、电站、P城
现在要从农场或电站或P城出发在渔村、矿场、学校中选择一个代价最小的顶点连到当前生成树中
由上图可知最小的代价为1如下图因此要把学校纳入生成树中 如上图在当前生成树下重复刚才的步骤此时的生成树中有农场、电站、P城、学校
现在要从农场或电站或P城或学校出发在渔村、矿场中选择一个代价最小的顶点连到当前生成树中
由上图可知最小的代价为4如下图因此可以把矿场或渔村纳入生成树中此时把矿场纳入生成树中这里把渔村纳入生成树后得出的最小生成树的最小代价一致 如上图在当前生成树下重复刚才的步骤此时的生成树中有农场、电站、P城、学校、矿场
现在要从农场或电站或P城或学校或矿场出发在渔村中选择一个代价最小的顶点连到当前生成树中
由上图可知最小的代价为2如下图因此可以把渔村纳入生成树中 最终得出了如上图所示的最小生成树最小代价也是15与例一、例二的最小代价一样。 四.求最小生成树-Kruskal算法(克鲁斯卡尔)
实例 执行过程每次选择一条权值最小的边使这条边的两头连通原本已经连通的就不选直到所有顶点连通。
以上述图片为例一开始图里的各个顶点都独立存在各个顶点之间不存在边所以用虚线标注
现在从所有的虚线里挑出权值最小的一条显然权值最小的是1这条虚线如下图 如上图1这条虚线的两头是P城和学校这两个顶点这两个顶点此时还没有连通所以把这条虚线选中使这两个顶点连通如下图 如上图继续从所有的虚线里挑出权值最小的一条显然权值最小的是2这条虚线如下图 如上图2这条虚线的两头是渔村和矿场这两个顶点这两个顶点此时还没有连通所以把这条虚线选中使这两个顶点连通如下图 如上图继续从所有的虚线里挑出权值最小的一条显然权值最小的是3这条虚线如下图 如上图3这条虚线的两头是农场和电站这两个顶点这两个顶点此时还没有连通所以把这条虚线选中使这两个顶点连通如下图 如上图继续从所有的虚线里挑出权值最小的一条显然权值最小的是4这条虚线如下图 如上图P城和矿场之间的虚线的权值、P城和渔村之间的虚线的权值都为4现在选择P城和矿场之间的虚线P城和矿场这两个顶点此时还没有连通所以把这条虚线选中P城和渔村这两个顶点此时也没有连通所以选这条虚线也可以使这两个顶点连通最终P城、矿场、渔村、学校这几个顶点就都连通了如下图 如上图继续从所有的虚线里挑出权值最小的一条显然权值最小的是4这条虚线如下图 如上图此时权值为4的这条虚线的两头是P城和渔村由于P城和渔村这两个顶点已经连通了所以这条虚线需要跳过不选如下图 如上图继续从所有的虚线里挑出权值最小的一条显然权值最小的是5这条虚线如下图 如上图P城和农场之间的虚线的权值、学校和矿场之间的虚线的权值都为5由于学校和矿场已经连通因此学校和矿场之间的虚线不选而P城和农场之间还没有连通所以应选中P城和农场之间的虚线如下图 如上图至此所有的顶点全部连通Kruskal算法(克鲁斯卡尔)结束。
如下图本例采用Kruskal算法(克鲁斯卡尔)得出的最小生成树的最小代价为15与用Prim算法(普里姆算法)得出的结果一致 五.Prim算法(普里姆算法) v.s. Kruskal算法(克鲁斯卡尔)
假设图中有V个顶点、E条边 对于Prim算法(普里姆算法)每一次是选择一个顶点开始
对于Kruskal算法(克鲁斯卡尔)每一次是选择一条边开始
因此这两个算法所表现出的时间复杂度也就不一样
Prim算法(普里姆算法)的时间复杂度只与顶点的个数有关适用于边稠密图即边多的图因为边多的话顶点相对少一些
Kruskal算法(克鲁斯卡尔)的时间复杂度只与边的个数有关适用于边稀疏图即边少的图因为边越少越能在短时间完成。 六.Prim算法的实现思想
1.实例 以上述图片为例假设从v0顶点开始设置isJoin数组和lowCost数组
isJoin数组用于记录图中的顶点是否被加入正在组建的生成树中由于刚开始v0已经在生成树中所以v0在isJoin数组的值为true上述图片标记为勾其余的顶点没有加入生成树中因此其余的顶点对应的值都为false上述图片标记为叉
lowCost数组用于记录把这些顶点加入到已经组建的生成树里所需要花费的最低代价-最开始选中了v0
由于v0与v0之间不存在边所以v0对应的lowCost数组的值为0
由于v0与v1之间有一条边这条边的权值为6因此把v1加入到组建的生成树中所需要付出的最低代价是6所以v1对应的lowCost数组的值为6
由于v0与v2之间有一条边这条边的权值为5因此把v3加入到组建的生成树中所需要付出的最低代价是5所以v2对应的lowCost数组的值为5
由于v0与v3之间有一条边这条边的权值为1因此把v2加入到组建的生成树中所需要付出的最低代价是1所以v3对应的lowCost数组的值为1
而v4与v5这两个顶点和v0之间都没有直接相连的边所以就目前来看暂时无法把v4、v5放到组建好的生成树中因此v4与v5对应的lowCost的值都用无穷记录也可以用别的记录。
如下图开始进行第一轮处理 首先需要检查isJoin数组和lowCost数组最终找出一个还没有被加入生成树且代价最低的顶点
由上述图片可知v3顶点没有加入生成树中且代价最小因此把v3顶点加入生成树中如下图 如上图要把v3顶点在isJoin数组中对应的值修改为true即勾表示已加入生成树中继续如下图 如上图需要循环遍历lowCost数组更新还没加入的各个顶点对应的lowCost值
现在加入了v3这个顶点之后对于其他的还没有被加入生成树的顶点接下来加入生成树的代价有可能会改变
因为生成树中相较于一开始多了个v3顶点最开始只有v0顶点时加入v1顶点最低代价为6现在多了个v3顶点加入v1顶点的最低代价为5显然小于6因此接下来如果要把v1加到生成树中所需要付出的最低代价就从6变成了5
因此把v1对应的lowCost值修改为5同理现在
加入v2的最低代价为4因此把v2对应的lowCost值修改为4
加入v4的最小代价为6因此把v4对应的lowCost值修改为6
加入v5的最小代价为4因此把v5对应的lowCost值修改为4
由于v0与v3这两个顶点已经加入到生成树中所以对应的lowCost值无需修改因为之后不会再加入v0与v3这两个顶点
最终lowCost数组中的值依次为0、5、4、1、6、4
如下图 如下图开始进行第二轮处理原理与第一轮一样 首先需要检查isJoin数组和lowCost数组最终找出一个还没有被加入生成树且代价最低的顶点
由上述图片可知v2顶点和v5顶点都没有加入生成树中且代价都是最小的代价都为4因此v2顶点和v5顶点都可以加入生成树中但如果是从头到尾去扫描lowCost数组中的元素v2顶点是第一个被挑选并加入生成树中的如下图 如上图要把v2顶点在isJoin数组中对应的值修改为true即勾表示已加入生成树中继续如下图 如上图需要循环遍历lowCost数组更新还没加入的各个顶点对应的lowCost值
由上述图片可知加入v2顶点之后
加入v1的最低代价为5无需修改
加入v4的最小代价为6无需修改
加入v5的最小代价为2因此把v5对应的lowCost值修改为2
由于v0、v3和v2这三个顶点已经加入到生成树中所以对应的lowCost值无需修改因为之后不会再加入v0、v3和v2这三个顶点
最终lowCost数组中的值依次为0、5、4、1、6、2
如下图 如下图开始进行第三轮处理 首先需要检查isJoin数组和lowCost数组最终找出一个还没有被加入生成树且代价最低的顶点
由上述图片可知v5顶点没有加入生成树中且代价最小因此把v5顶点加入生成树中如下图 如上图要把v5顶点在isJoin数组中对应的值修改为true即勾表示已加入生成树中继续如下图 如上图需要循环遍历lowCost数组更新还没加入的各个顶点对应的lowCost值
由上述图片可知加入v5顶点之后
加入v1的最低代价为5无需修改
加入v4的最小代价为6无需修改
由于v0、v3、v2和v5这四个顶点已经加入到生成树中所以对应的lowCost值无需修改因为之后不会再加入v0、v3、v2和v5这四个顶点
最终lowCost数组中的值依次为0、5、4、1、6、2
如下图 如下图开始进行第四轮处理 首先需要检查isJoin数组和lowCost数组最终找出一个还没有被加入生成树且代价最低的顶点
由上述图片可知v1顶点没有加入生成树中且代价最小因此把v1顶点加入生成树中如下图 如上图要把v1顶点在isJoin数组中对应的值修改为true即勾表示已加入生成树中继续如下图 如上图需要循环遍历lowCost数组更新还没加入的各个顶点对应的lowCost值
由上述图片可知加入v1顶点之后
加入v4的最小代价为3因此把v4对应的lowCost值修改为2
由于v0、v3、v2、v5和v1这五个顶点已经加入到生成树中所以对应的lowCost值无需修改因为之后不会再加入v0、v3、v2、v5和v1这五个顶点
最终lowCost数组中的值依次为0、5、4、1、3、2 如下图开始进行第五轮处理 首先需要检查isJoin数组和lowCost数组最终找出一个还没有被加入生成树且代价最低的顶点
由上述图片可知v4顶点没有加入生成树中且代价最小因此把v4顶点加入生成树中如下图 如上图要把v4顶点在isJoin数组中对应的值修改为true即勾表示已加入生成树中
最终所有顶点全部加入到生成树中Prim算法结束。
2.时间复杂度分析 上述例子中进行了好几轮的处理最终得出最小生成树从代码角度来看就是好几轮的循环
由于每一轮的循环都会选择一个新的顶点把它放入生成树中假设图中有n个顶点就需要n-1轮的循环因为第一个顶点不需要循环
而每一轮的处理当中又需要进行两次循环遍历第一次循环遍历所有的顶点来从isJoin数组和lowCost数组中找出未加入生成树且代价最小的顶点第二次循环遍历所有的顶点来更新lowCost数组所以每一轮的时间复杂度为O(2n)等价于O(n)
由于需要n-1轮循环所以总的时间复杂度就是O( n * (n-1) )等价于O( n * n - n )等价于O( n * n )
如果改为图中有V个顶点时间复杂度就是O( |V| * |V|)。 七.Kruskal算法(克鲁斯卡尔)的实现思想
1.实例
如下图由于Kruskal算法(克鲁斯卡尔)每次要选择一条权值最小的边所以要先把各条边按照权值递增的次序进行排序 如上图权值最小的边是权值为1的这条边两边的顶点是v0和v3所以上述图片里的第一行数据中weight为1、Vertex1为v0、Vertex2为v3该算法的执行过程就是把所有的边都检查一遍。 如上图第一条边的权值为1两边连的顶点是v0和v3接下来就要检查v0和v3是否连通进行这个判断用到了并查集详情见5.15.并查集大致的思想就是刚开始要把所有的顶点分别看作是不同的集合所以对于第一条边的两个顶点v0和v3他们刚开始从属于不同集合也就意味着他们此时不连通因此就可以把这条边选中如下图 此时v0和v3这两个顶点就属于同一个集合了
如下图接下来进行第二轮的处理权值为2的边的两头为v2和v5v2和v5此时不属于同一个集合即v2和v5不连通所以把v2和v5连起来把v2和v5归并为同一个集合 如下图接下来进行第三轮的处理权值为3的边的两头为v1和v4v1和v4此时不属于同一个集合即v1和v4不连通所以把v1和v4连起来把v1和v4归并为同一个集合 如下图接下来进行第四轮的处理其中一条权值为4的边的两头为v2和v3v2和v3此时不属于同一个集合即v2和v3不连通所以把v2和v3连起来把v2和v3归并为同一个集合 如下图接下来进行第五轮的处理其中一条权值为4的边的两头为v3和v5v3和v5此时属于同一个集合即v3和v5连通所以v3和v5之间的边会跳过不选中 接下来的过程同理最终把v1与v3连接后就得出最小生成树
如下图总之就是要把所有的边都遍历一遍每当处理一条边时需要判断这条边所连接的两个顶点是否从属于同一个集合如果不是那就把这条边选中如果是就不选中 2.时间复杂度分析
假设图中共有e条边 每轮循环中判断两个顶点是否属于同一个集合要用到并查集这个过程的时间复杂度详情见5.15.并查集共e轮。 八.总结
