通过图获取路径列表

Question

我想通过具有给定出发点和目的地的图来获取所有可能路径列表的列表。 该图给出如下：

data Node = N1 | N2 | N3 | N4 | N5 deriving (Show, Eq) 

neighbor :: Node -> [Node] 
neighbor N1 = [N2, N4, N5] 
neighbor N2 = [N1, N3] 
neighbor N3 = [N1, N4, N5] 
neighbor N4 = [N5] 
neighbor N5 = [N1] 

的问题是：给定一个起始节点和目的地节点（例如启动节点= N1和目的地= N4）所有可能的路由，而无需循环，从开始导致目的地应该是结果。在给出的例子将是：

[[N1, N2, N3, N4],[N1, N4]] 

功能我想用是解决这个问题：

generatePaths :: (Node -> [Node]) -> Node -> Node -> [[Node]] 

这里的第一个参数应为邻居功能，第二起始节点和第三个目的地节点。

我的主要问题是，我现在找到如何遍历所有邻居，并呼吁每个邻居作为新的开始节点generatePaths。

任何帮助，高度赞赏

编辑： THX到克罗姆和路跑我想出了一个实现。

dfs_h :: (Node -> [Node]) -> [Node] -> [Node] -> Node -> [[Node]] 
dfs_h graph visited [] _ = [visited] 
dfs_h graph visited (n:ns) end 
    | elem n visited = (dfs_h graph visited ns end) 
    | elem end ns = [reverse (end:visited)] ++ (dfs_h graph visited (n:[neigh|neigh <- ns, neigh /= end]) end) 
    | n == end = [reverse (end:visited)] ++ (dfs_h graph visited ns end) 
    | otherwise = dfs_h graph (n:visited) ((graph n) ++ ns) end 

dfs start end = filter (\x -> elem end x) (dfs_h neighbor [start] (neighbor start) end       

我知道这不是最美的解决方案，只是我想出的第一个。

EDIT2： 但是这个算法的一个问题是，当图如下所示：

neighbor :: Node -> [Node] 
neighbor N1 = [N2, N3] 
neighbor N2 = [N5] 
neighbor N3 = [N4] 
neighbor N4 = [N2, N1] 
neighbor N5 = [N1] 

和N1到N4的路径将被找到，那么函数的结果是

[[N1, N2, N5, N3, N4]] 

现在我不知道如何实施，以便N2和N5（不应该是解决方案的一部分）不包含在内。 任何建议？

Answer 1

您的递归步骤

| otherwise = dfs_h graph (n:visited) ((graph n) ++ ns) end 

看起来怪怪的。您尝试处理n是您路径上的有效中间节点的情况。对于递归，您因此在visited日志中收集n。问题是ns - 当前步骤中的其他中间节点列表 - 将在递归步骤中处理。相反，它应该使用未修改的当前访问节点集处理。

一个更简单的解决办法是分开您从计算的中间结果记录：

generatePaths :: (Node -> [Node]) -> Node -> Node -> [[Node]] 
generatePaths successors start end = map reverse $ dfs [] [[]] start 
    where 
    dfs :: [Node] -> [[Node]] -> Node -> [[Node]] 
    dfs visited acc next 
     -- destination reached, add final step 
     | next == end = step next acc 
     -- circle detected, reject paths 
     | next `elem` visited = [] 
     -- make one step, continue recursion 
     | otherwise = concat . map (dfs (next:visited) (step next acc)) $ successors next 

    -- add `next` to each of the current paths 
    step :: Node -> [[Node]] -> [[Node]] 
    step next = map ((:) next)