最小生成树

问题

对于给出的一张图 $G(V,E)$ 求一个生成子图 $G'(V,E')$ 使得 $\sum_{e\in E'}W_{e_i}$ 最小，其中 $W_{e_i}$ 表示边 $e_i$ 的边权
这里用一个在线画图工具来作图：传送门

解析

最小生成树问题其实就是在一张图中扣出一棵树来，这棵树有最小的边权和
对于最小生成树问题有两种常用的方法，一是kurskal算法，二是prim算法，下面给出两种算法的推导与图示

Kruskal

算法流程

1.对图 $G$ 的所有边，按边权升序排序
2.从小到大遍历所有的边
3.对于边 $e$ ，若他的两个端点不在同一个集合内，将 $e$ 加入答案集合，并将他的两条边放入同一个集合，否则跳过
4.遍历完所有的边或答案集合中有 $n-1$ 条边时，算法结束，其中 $n$ 是图 $G$ 的边数

tips

1.可以用一个三元组 $(u,v,w)$ 来储存图中的边，其中 $u,v$ 是边的两个端点， $w$ 是边权
2.对于图的联通性，可以用并查集维护，每次查询 $u,v$ 是否属于同一个集合

算法流程图示

1.给出一张图 $G$

2.一开始是一张空图

3.按照边权的升序，加入一条边 $(1,3,1)$ ,判断 $1,3$ 并不属于同一个集合，放心加入

4.同理，加入边 $(1,5,2)$

5.同理，加入边 $(1,6,3)$

6.同理，加入边 $(5,2,4)$

7.尝试加入边 $(2,6,5)$ ，发现 $2,6$ 在同一个集合内，不加入这条边

8.边 $(3,4,6)$ 又是一条符合条件的边，加入，算法结束

prim

算法流程

1.选定一个起点加入答案集合
2.遍历从这集合内的点连向未加入集合的所有点的边，选定一条边权最小的点，加入集合
3.重复操作2直到没有更多的点可以加入

tips

1.采用邻接表存图
2.用一个 $vis_i$ 来表示点 $i$ 是否在集合内
3.采用优先队列可以提高算法的效率

算法流程图示

以 $6$ 作为起点
1.一张空图

2.以6为起点，将6加入答案集合，从集合连出的所有边中 $(1,6,1)$ 边权最小，将 $1$ 加入

3.此时答案集合为 $\{1,6\}$ ,从集合连出的所有边中 $(1,3,1)$ 边权最小，将 $3$ 加入答案集合

4.答案集合变为 $\{1,3,6\}$ ,从集合连出的所有边中 $(1,5,2)$ 边权最小，将 $5$ 加入答案集合

6.答案集合变为 $\{1,3,5,6\}$ ,从集合连出的所有边中 $(2,5,4)$ 边权最小，将 $2$ 加入答案集合

7.答案集合变为 $\{1,2,3,5,6\}$ ,从集合连出的所有边中 $(3,4,6)$ 边权最小，将 $4$ 加入答案集合

设计(伪代码)

kruskal

tot=0
count_edge=0
sort(E,key=edge.weight)
for 所有集合E中的边:
    if edge的两个端点在同一个集合中:
        continue
    else:
        count_edge+=1
        tot+=edge.w
        合并edge的两个端点所在的集合
    if count_edge==V.size-1:
        break
return tot

在实际使用中如果边不多，可以不需要统计生成树内的边的数量，因为算法保证了不会出现环

prim

tot=0
set={1}
q={(v,w)|edge[i].u=1}
while set.size < n:
    cur=q中边权最小的点
    tot+=cur.w
    for 所有与cur.v相连的点t：
        if t在set中:
            continue
        else:
            向q中插入(q,W)
    在set中插入cur.v
return tot

可以按边权维护一个小顶堆作为优先队列，每次弹出队首的点加入集合，并访访问所有与该点相联的店，若不在集合中则加入优先队列

分析

在此约定图 $G$ 的点数为 $n$ ，边数为 $m$

kruskal

kruskal算法主要分为两部分，一是对边进行排序，二是枚举边同时对点进行集合的合并
对边进行排序可以使用快速排序，归并排序，堆排序等等较为优秀的排序算法，这部分复杂度为 $O(m\log(m))$
枚举边的复杂度为 $O(m)$ 对点进行集合合并使用并查集来完成，加上并查集后的复杂度很难计算，通过网上查询发现其复杂度大约 $O(m\log_{1+m/n}^n)$ ,可以明确的是小于排序的复杂度 $O(m\log(m))$ 的
最终复杂度由最高次决定，因此整个算法的复杂度为 $O(m\log(m))$

prim

prim算法的主要过程有枚举点和找到最短边
首先每个点只会被插入答案集合中一次，因此可以发现这部分的复杂度是 $O(n)$ 的
同时对于是否在集合中的判断可以通过数组标记来实现，这部分 $O(1)$
对于每插入一个点，我们都需要找到此时联通内外的边，枚举所有点，这部分 $O(n)$
最后复杂度为 $O(n^2)$
但是我们可以用优先队列来优化找最小边的过程，优先队列插入的复杂度为 $O(\log(m))$ ，查询的复杂度为 $O(1)$ ，整张图共有 $n$ 个点，所以这部分复杂度是 $O(n\log(m))$
总的复杂度为 $O(n\log(m))$

算法课-最小生成树

最小生成树

问题

解析

Kruskal

算法流程

tips

算法流程图示

prim

算法流程

tips

算法流程图示

设计(伪代码)

kruskal

prim

分析

kruskal

prim

源码