Question

最小生成树实际应用的例子

Answer 1

最小生成树实际应用的例子如下：

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棵树的一个森林。