1. 加权无向图和最小生成树
1.1. 基本介绍
加权图是指为每条边关联一个权值或者成本的图,应用广泛。这个章节里我们关注加权无向图。无环连通图是树,而一个图中包含所有顶点的无环连通子图为生成树,一幅加权图中的所有边权值之和最小的生成树为最小生成树(MST)。
针对这里的讨论我们提前做出如下约定:
1.只考虑连通图。
2.边的权值不一定代表距离。
3.边的权重可能为0或者负数。
4.所有边的权重各不相同。(使得MST唯一,但实际不影响)
接下来,我们讨论树的一些基本性质。
1.用一条边连接树的任意两个顶点都会产生一个新的环。
2.从树中删去一条边将会得到两个独立的树。
这两个基本性质是证明另外一个基本性质的基础,也能由此证明本章的会介绍的两个算法。
1.2. 切分定理
1.2.1. 基本概念介绍
图的切分是将图的所有顶点分为两个非空不重叠的子集。横切边是两个属于不同子集的顶点的边。通常我们指定一个顶点集并隐式的认为其补集为另一个子集构成切分。
1.2.1. 定理介绍和证明
在一幅加权图中,对于任意一个切分,其横切边权值最小的必然属于最小生成树。
证明:
首先最小生成树必须有这个切分的至少一条横切边,否则就变成多颗树,不可能是单独的一棵树。现在假设e是权值最小的一条横切边,f为另一条横切边。如果最小生成树不含有e,而含有f,那么加上e成环,去掉环的一条边仍然是一个生成树树,我们去掉f就能得到一个权值更小的生成树,这和我们假设矛盾,证毕。
1.2.3. 得到最小生成树的算法原理
实质上将会使用的算法都是贪心算法的一种特殊情况:使用切分定理找到MST的一条边,不断重复直到找齐为止。
1.3. 加权无向图的实现
我们依旧采用邻接表的形式实现它,但是会对基本元素进行扩展,这一次我们的基本元素不再是顶点而是边。
一个边它包含有两个顶点一个权值,我们还为边提供了返回权值,返回顶点等方法。实现如下:
1 | class Edge |
有了边的数据结构,在此基础上实现加权无向图就和之前的代码差不多,只是基本元素换成了边。代码如下:
1 | class EdgeWeightGraph |
2. 算法部分
2.1. Prim算法
有了以上的基础,对于最小生成树算法的理解就要容易多了。首先要介绍的是Prim算法,他一开始是只有一个顶点,每次操作都会将下一条连接在树中和不在树中的顶点的权重最小的边加入树中。根据切分定理易得其正确性。
现在分析其代码实现策略,对于顶点我们可以使用之前的marked数组来表示其是否在树中,对于MST的边,我们可以用队列,edgeTo数组来储存边,对于横切边,因为要不断选出最小的横切边,我们使用优先队列来储存并操作。
其中有一些需要注意的细节,每当我们加入一条边,也就同时加入了一个顶点。那么横切边的合集就需要更新,也就需要将连接这个顶点和其他不在树中的顶点的边加入优先队列。但要注意,连接新加入的点和原来的树的边失效。我们可以删除它也可以不删除他,故引出了两种Prim算法,延时的和即时的。
延时部分如下所示:
1 | class LazyPrimMST |
即时部分与之的最大区别就是,它对于树之外的顶点,永远只保存它连接数的边中权值最小,由于大部分策略相似,这里不展示代码了。
Prim算法的空间消耗与V成正比,所需时间与ElogV成正比。(V为顶点数,E为边数)
2.2. Kruskal算法
这个算法的原理是按照边的权重顺序从小到大处理,加入最小生成树中,加入的边不会和原有的MST中的边成环。同样使用切分定理可以快速证明。代码如下:
1 | class KruskalMST |
Kruskal算法计算V顶点,E条边的加权无向图时,所需空间和E成正比,时间和ElogE成正比。一般比Prim算法要慢。