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)]