我需要构建一个函数,它返回特定节点之间的所有路径。
connect::Int -> Int-> [[(Int,Int)]]
Data.Graph 库为我提供了有用的函数“buildG”,它可以为我构建图表。如果我打电话
让 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)]]
最佳答案
递归思考。从 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]
从节点到自身的所有符合条件的路径列表是单个元素[]
的列表,在其他情况下,我们通过上面的逻辑获取所有符合条件的路径列表,pick第一条边并找到从它的末端开始的路径。
问题是循环会导致它挂起。为避免这种情况,您必须记住您已经访问过哪些节点,而不是从那里开始探索路径:
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)]
关于Haskell - 生成节点之间的所有路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11168238/