P81 - 两点间所有无环路径
Find all acyclic paths between two vertices
官方模块：
Problems.P81核心函数：paths
实现
DFS 的状态包含当前路径已访问顶点。每条递归分支都有自己的 visited，所以一条分支的选择不会污染其他候选路径。
方法一：DFS 回溯
1neighbors :: Vertex -> G -> Set.Set Vertex
2neighbors v (G graph) = Map.findWithDefault Set.empty v graph
3
4paths :: Vertex -> Vertex -> G -> [[Vertex]]
5paths start target graph = go start Set.empty
6 where
7 go current visited
8 | current == target = [[target]]
9 | Set.member current visited = []
10 | otherwise =
11 [current : rest
12 | next <- Set.toList (neighbors current graph)
13 , rest <- go next (Set.insert current visited)]
方法二：按长度扩展路径（BFS）
1pathsBreadthFirst :: Vertex -> Vertex -> G -> [[Vertex]]
2pathsBreadthFirst start target graph = expand [[start]]
3 where
4 expand [] = []
5 expand frontier = completed ++ expand nextFrontier
6 where
7 completed = [path | path <- frontier, last path == target]
8 unfinished = [path | path <- frontier, last path /= target]
9 nextFrontier =
10 [path ++ [next]
11 | path <- unfinished
12 , next <- Set.toAscList (neighbors (last path) graph)
13 , next `notElem` path]
frontier 中的路径长度始终相同，因此结果按边数从少到多产生。路径自身就是访问集合，扩展时禁止加入已经出现的顶点。与 DFS 相比，它更早得到短路径，但会同时保存大量候选路径。
方法对比
| 方法 | 输出顺序 | 内存 |
|---|---|---|
| DFS | 先完整探索一条分支 | 与递归深度和输出有关 |
| BFS | 按路径长度递增 | 需要保存整层候选路径 |
测试
1>>> let graph = toG (Paths [[1,2,3],[1,3,4,2],[5,6]])
2>>> sort (paths 1 4 graph)
3[[1,2,3,4],[1,2,4],[1,3,2,4],[1,3,4]]
4>>> paths 2 6 graph
5[]
6>>> paths 1 1 graph
7[[1]]
8>>> sort (pathsBreadthFirst 1 4 graph) == sort (paths 1 4 graph)
9True
简单路径数量在稠密图中可能是指数级，算法成本至少与输出总长度成正比。