P88 - 图的连通分量
Connected components
官方模块：
Problems.P88核心函数：connectedComponents
思路与实现
方法一：标准解法
从尚未归类的最小顶点出发做 P87 的 DFS，所得可达集合就是一个连通分量；从剩余顶点中删除它并重复。
1connectedComponents :: G -> [[Vertex]]
2connectedComponents graph = collect allVertices
3 where
4 allVertices = fst (canonical graph)
5 collect remaining
6 | Set.null remaining = []
7 | otherwise = component : collect
8 (Set.difference remaining (Set.fromList component))
9 where
10 component = depthFirst graph (Set.findMin remaining)
方法二：逐边合并分量
1connectedComponentsByEdges :: G -> [[Vertex]]
2connectedComponentsByEdges graph =
3 map Set.toAscList (foldl mergeEdge initial (Set.toList edges))
4 where
5 (vertices, edges) = canonical graph
6 initial = map Set.singleton (Set.toList vertices)
7
8 mergeEdge components (u, v)
9 | componentU == componentV = components
10 | otherwise = Set.union componentU componentV
11 : filter (\component -> component /= componentU && component /= componentV)
12 components
13 where
14 componentU = componentOf u components
15 componentV = componentOf v components
16
17 componentOf vertex = head . filter (Set.member vertex)
初始时每个顶点各自形成分量。每读取一条边，就合并端点所在集合；所有边处理完后，剩余集合正是连通分量。这与按顶点执行 DFS 的方法形成对照。
方法对比
| 方法 | 输入驱动 |
|---|---|
| 重复 DFS | 从尚未访问的顶点扩展 |
| 逐边合并 | 由边连接顶点集合 |
测试
1>>> let graph = toG (Paths [[1,2,3,4,5],[2,4],[6,7]])
2>>> sort (map sort (connectedComponents graph))
3[[1,2,3,4,5],[6,7]]
4>>> connectedComponents (toG (Lists ([],[])))
5[]
6>>> sort (map sort (connectedComponentsByEdges graph))
7[[1,2,3,4,5],[6,7]]
各次 DFS 访问的顶点集合互不相交，整体复杂度仍为 。