Haskell中 - 產生節點

Question

我需要建立一個函數，該函數返回某些節點之間的所有路徑之間的所有路徑。

connect :: Int -> Int-> [[(Int,Int)]]

Data.Graph圖書館給我有用的功能 'buildG' 它建立圖形我。如果我叫

let g = buildG (1,5) [(1,2),(2,3),(3,4),(4,5),(2,5)]，

我會得到，每一個節點被映射到他的鄰居的數組。 一個例子：

g!1 = [2] 
g!2 = [3,5] 
.. 
g!5 = [] 

我嘗試使用列表理解來做到這一點，但我不是在Haskell很好，我 我不能得到修復打字錯誤。

connect x y g 
    | x == y = [] 
    | otherwise = [(x,z) | z <- (g!x), connect z y g] 

我現在不需要擔心這個週期。這是我想要得到的：

connect 1 5 g = [[(1,2),(2,3),(3,4),(4,5)],[(1,2),(2,5)]] 

Answer 1

遞歸地思考。從s到e的路徑由第一邊緣和(s,t)t從到e的路徑的，除非s == e，在這種情況下的路徑應爲空。這樣的第一嘗試是

connect x y g 
    | x == y = [[]] 
    | otherwise = [(x,t):path | t <- g!x, path <- connect t y g] 

從自身節點的所有合格的路徑的列表是與單個元件[]列表中，在其他情況下，我們通過邏輯獲得上述所有符合條件的路徑的列表，選擇第一條邊並從末端找到路徑。

的問題是，週期將導致其掛起。爲了避免這種情況，你必須記住你已經訪問過哪些節點，而不是探索那些路徑：

connect x y g = helper x y g [x] 
    where 
    helper a b g visited 
     | a == b = [[]] 
     | otherwise = [(a,c):path | c <- g!a, c `notElem` visited, path <- helper c b g (c:visited)]