通過圖獲取路徑列表

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)