4

我需要构建一个函数，它返回某些节点之间的所有路径。

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

1 回答 1

6

递归思考。从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)]
于 2012-06-23T09:26:47.873 回答