P84 - 用 Prim 算法构造最小生成树

Construct a minimum spanning tree
官方模块：Problems.P84　核心函数：minimumSpanningTree

算法

从任意顶点开始，反复选择连接“树内”和“树外”的最小权边。加入这条边不会产生环；连通图在加入 $n-1$ 条边后覆盖全部顶点。

实现

方法一：Prim 贪心

 1minimumSpanningTree :: G -> Map.Map Edge Int -> G
 2minimumSpanningTree graph weights
 3  | Set.null vs = graph
 4  | otherwise   = grow (Set.singleton (Set.findMin vs)) []
 5  where
 6    (vs,es) = canonical graph
 7    grow inside chosen
 8      | inside == vs = toG (Lists (Set.toList vs, chosen))
 9      | null crossing = toG (Lists ([],[]))
10      | otherwise =
11          let edge@(u,v) = minimumByWeight crossing
12              newVertex = if Set.member u inside then v else u
13          in grow (Set.insert newVertex inside) (edge : chosen)
14      where
15        crossing = [e | e@(u,v) <- Set.toList es
16                       , Set.member u inside /= Set.member v inside]
17
18    minimumByWeight = minimumBy
19      (comparing (\edge -> Map.findWithDefault 0 edge weights))

需要导入 Data.List (minimumBy) 和 Data.Ord (comparing)。权重映射的键必须使用 P80 的规范化无向边。

方法二：Kruskal 算法

 1import Data.List (sortOn)
 2
 3minimumSpanningTreeKruskal :: G -> Map.Map Edge Int -> G
 4minimumSpanningTreeKruskal graph weights =
 5  choose sortedEdges initialComponents []
 6  where
 7    (vertices, edges) = canonical graph
 8    sortedEdges = sortOn edgeWeight (Set.toList edges)
 9    edgeWeight edge = Map.findWithDefault 0 edge weights
10    initialComponents = map Set.singleton (Set.toList vertices)
11
12    choose [] _ chosen
13      | length chosen == Set.size vertices - 1 = build chosen
14      | Set.null vertices = build []
15      | otherwise = toG (Lists ([], []))
16    choose (edge@(u, v):rest) components chosen
17      | componentU == componentV = choose rest components chosen
18      | otherwise = choose rest merged (edge : chosen)
19      where
20        componentU = componentOf u components
21        componentV = componentOf v components
22        merged = Set.union componentU componentV
23               : filter (\component -> component /= componentU && component /= componentV)
24                        components
25
26    componentOf vertex =
27      head . filter (Set.member vertex)
28
29    build chosen = toG (Lists (Set.toList vertices, chosen))

Kruskal 按权重从小到大检查边。这里用顶点集合列表表示连通分量：端点已经属于同一分量时跳过该边，否则合并两个分量。它比并查集版本短，但每次查找和合并分量都是线性的。

方法对比

方法	生长方式	当前实现复杂度
Prim	从一个顶点向外扩展	O(nm)
Kruskal	按全局边权合并分量	O(m log m + mn)

测试

1>>> let g = toG (Paths [[1,2,3],[1,3]])
2>>> let w = Map.fromList [((1,2),5),((2,3),1),((1,3),2)]
3>>> canonical (minimumSpanningTree g w)
4(fromList [1,2,3],fromList [(1,3),(2,3)])
5>>> canonical (minimumSpanningTreeKruskal g w)
6(fromList [1,2,3],fromList [(1,3),(2,3)])

当前版本每轮线性扫描所有边，复杂度 $O(nm)$ ；使用优先队列可优化到 $O(m\log n)$ 。

参考

← P83 生成树 | P85 图同构 →