P82 - 包含指定顶点的所有环
Find cycles containing a given vertex
官方模块：
Problems.P82核心函数：cycles
思路与实现
从目标顶点的每个邻居出发做 DFS。允许最后回到起点，但在此前不能重复顶点；长度 2 的立即折返不算无向图中的环。
方法一：专用 DFS 回溯
1cycles :: Vertex -> G -> [[Vertex]]
2cycles start graph =
3 [reverse path
4 | next <- Set.toList (neighbors start graph)
5 , path <- walk next (Set.singleton start) [start]]
6 where
7 walk current visited reversedPath
8 | current == start =
9 [reversedPath | length reversedPath >= 3]
10 | Set.member current visited = []
11 | otherwise = concat
12 [walk next (Set.insert current visited) (current : reversedPath)
13 | next <- Set.toList (neighbors current graph)]
结果不重复末尾的起点，并且顺时针、逆时针被视为两条不同遍历，这与官方示例一致。
方法二：复用 P81 的简单路径
1cycles :: Vertex -> G -> [[Vertex]]
2cycles start graph =
3 [start : init path
4 | next <- Set.toList (neighbors start graph)
5 , path <- paths next start graph
6 , length path >= 3
7 ]
P81 的 paths next start graph 已经保证路径中不重复顶点。去掉路径末尾重复的 start，再把起点放回开头，就得到包含指定顶点的环。长度过滤排除了无向边上的立即折返。
方法对比
| 方法 | 特点 |
|---|---|
| 专用 DFS | 一次搜索直接生成环，状态最少 |
| 复用简单路径 | 组合已有函数，定义更短但会生成并过滤长度 2 的路径 |
测试
1>>> let graph = toG (Paths [[1,2,3],[1,3,4,2],[5,6]])
2>>> sort (cycles 1 graph)
3[[1,2,3],[1,2,4,3],[1,3,2],[1,3,4,2]]
4>>> cycles 5 graph
5[]