发布网友 发布时间:2023-06-19 00:33
共1个回答
热心网友 时间:2023-09-22 07:48
最小生成树实际应用的例子如下:
Kruskal算法,过程描述:始终以边为主导地位,先选择权值最小的边,总是选择当前可用最小权值边,并且每次判断两点之间是否已经间接连通,如果已经间接连通,则跳过此边。时间复杂度是O(n*logn),适用于求边稀疏连通网的最小生成树。
Prim算法,过程描述:Prim算法始终以顶点为主导,并且起始点的选择是任意的。从起始点到其他点选择最小权值边,然后以此边两个顶点分别再找最小权值的边,同样已经间接连接的边跳过。时间复杂度是O(n2),适用于求边稠密连通网的最小生成树。
要在n个城市之间铺设光缆,主要目标是要使这n个城市的任意两个之间都可以通信,但铺设光缆的费用很高,且各个城市之间铺设光缆的费用不同,因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。
最小生成树性质与算法简述:
最小生成树性质:设G=(V,E)是一个连通网络,U是顶点集V的一个非空真子集。若(u,v)是G中一条“一个端点在U中(例如:u∈U),另一个端点不在U中的边(例如:v∈V-U),且(u,v)具有最小权值,则一定存在G的一棵最小生成树包括此边(u,v)。
将集合U中的顶点看作是红色顶点,②而V-U中的顶点看作是蓝色顶点,③连接红点和蓝点的边看作是紫色边,④权最小的紫边称为轻边(即权重最“轻”的边)。于是,MST性质中所述的边(u,v)就可简称为轻边。
求MST的一般算法可描述为:针对图G,从空树T开始,往集合T中逐条选择并加入n-1条安全边(u,v),最终生成一棵含n-1条边的MST。
Kruskal算法简述:假设WN=(V,{E})是一个含有n个顶点的连通网,则按照克鲁斯卡尔算法构造最小生成树的过程为:先构造一个只含n个顶点,而边集为空的子图,若将该子图中各个顶点看成是各棵树上的根结点,则它是一个含有n棵树的一个森林。