P83 - 构造所有生成树

Construct all spanning trees
官方模块：Problems.P83　核心函数：spanningTrees、isTree、isConnected

判定基础

含 $n$ 个顶点的无向图是树，当且仅当它连通且恰有 $n-1$ 条边。因此生成树可从原图边集中选择 $n-1$ 条，再过滤连通候选。

方法一：组合后过滤

 1isConnected :: G -> Bool
 2isConnected graph
 3  | Set.null vs = True
 4  | otherwise   = reachable (Set.findMin vs) == vs
 5  where
 6    (vs,_) = canonical graph
 7    reachable start = visit Set.empty [start]
 8    visit seen [] = seen
 9    visit seen (v:stack)
10      | Set.member v seen = visit seen stack
11      | otherwise = visit (Set.insert v seen)
12          (Set.toList (neighbors v graph) ++ stack)
13
14isTree :: G -> Bool
15isTree graph = isConnected graph && Set.size es == max 0 (Set.size vs - 1)
16  where (vs,es) = canonical graph
17
18spanningTrees :: G -> [G]
19spanningTrees graph
20  | Set.null vs = []
21  | otherwise =
22      [tree | chosen <- combinations (Set.size vs - 1) (Set.toList es)
23            , let tree = toG (Lists (Set.toList vs, chosen))
24            , isConnected tree]
25  where (vs,es) = canonical graph

方法二：增量合并连通分量

 1spanningTreesIncremental :: G -> [G]
 2spanningTreesIncremental graph
 3  | Set.null vertices = []
 4  | otherwise =
 5      [toG (Lists (Set.toList vertices, chosen))
 6      | chosen <- grow (Set.toList edges) initialComponents []]
 7  where
 8    (vertices, edges) = canonical graph
 9    target = Set.size vertices - 1
10    initialComponents = map Set.singleton (Set.toList vertices)
11
12    grow remaining components chosen
13      | length chosen == target =
14          [reverse chosen | length components == 1]
15      | length chosen + length remaining < target = []
16    grow [] _ _ = []
17    grow (edge@(u, v):rest) components chosen =
18      grow rest components chosen ++ include
19      where
20        componentU = componentOf u components
21        componentV = componentOf v components
22        include
23          | componentU == componentV = []
24          | otherwise = grow rest merged (edge : chosen)
25        merged = Set.union componentU componentV
26               : filter (\component -> component /= componentU && component /= componentV)
27                        components
28
29    componentOf vertex = head . filter (Set.member vertex)

每加入一条边就合并两个连通分量；若端点已经在同一分量，加入它一定成环，可以立刻剪枝。选满 $n-1$ 条边时只需检查是否剩一个分量，不必重新执行 DFS。

方法对比

方法	候选检查
组合后过滤	先选满 n-1 条边，再检查连通性
增量合并	选边时立即排除环和边数不足分支

测试

1>>> isTree (toG (Paths [[1,2,3],[1,4,5]]))
2True
3>>> isConnected (toG (Lists ([1,2,3],[])))
4False
5>>> length (spanningTrees (toG (Paths [[1,2,3,1]])))
63
7>>> length (spanningTreesIncremental (toG (Paths [[1,2,3,1]])))
83

组合枚举最坏需要检查 $\binom{m}{n-1}$ 个候选，适合练习而非大型图。

参考

← P82 包含指定顶点的环 | P84 最小生成树 →