基于Haskell自定义图类型实现无环路径枚举函数paths的求助

嘿，咱们先把题目给定的基础定义和示例图明确下来，这是实现的前提：

类型定义 #

type Node = Integer
type Edge = (Integer, Integer)
type Graph = [Edge]
type Path = [Node]

示例图 #

g :: Graph
g = [(1,2), (1,3), (2,3), (2,4), (3,4)]

h :: Graph
h = [(1,2), (1,3), (2,1), (3,2), (4,4)]

实现paths函数 #

要生成所有从起点到终点的无环路径，核心就是不能走回头路——得时刻记住已经访问过哪些节点。我写了个带辅助函数的实现，主函数负责初始化参数，递归逻辑交给辅助函数处理：

完整代码 #

paths :: Node -> Node -> Graph -> [Path]
paths start end graph = pathsHelper start end graph [start] [start]
  where
    pathsHelper :: Node -> Node -> Graph -> [Node] -> [Node] -> [Path]
    -- 递归终止：当前节点就是终点，返回这条有效路径
    pathsHelper curr end _ _ path | curr == end = [path]
    pathsHelper curr end graph visited path =
      -- 筛选出所有从当前节点出发、且未被访问过的下一个节点
      let nextNodes = [to | (from, to) <- graph, from == curr, to `notElem` visited]
      -- 对每个下一个节点递归探索，最后合并所有路径
      in concatMap (\next -> pathsHelper next end graph (next:visited) (path ++ [next])) nextNodes

代码拆解 #

• 主函数paths初始化已访问列表为[start]（一开始只有起点被走过），当前路径也设为[start]，然后调用辅助函数。
• 辅助函数的终止条件很直观：如果当前节点就是终点，直接返回这条路径。
• 非终止情况时，先筛选出符合要求的下一个节点（必须是当前节点的邻接点，且没被访问过），然后对每个节点递归探索，把所有递归得到的路径合并成一个大列表。

测试验证 #

调用paths 1 4 g的预期输出是：

[[1,2,3,4],[1,2,4],[1,3,4]]

（给定的图g里，这就是所有从1到4的无环路径啦）

内容的提问来源于stack exchange，提问作者nwelch