提供一个复制图形边缘列表的列表,我想在Haskell上创建一个函数,如果有一个从节点A到B的路径,它返回true . 我的函数似乎在大多数情况下有效,但它有时永远不会结束 . 我知道我必须保留一个列表与访问过的节点,但我是Haskell的新手,我不知道如何实现这一点,因为递归 . 你能帮助我吗?
-- the successor of a node, ex for the edge (1,2) the succ of 1 is 2
suc x [] = 0
suc x (l:list) =
if(x==(fst l)) then snd l
else suc x list
path 0 y list = False
path x y (mu:m)
| x==y = True
| otherwise =
if ((path (suc x (mu:m)) y (mu:m))==False) then path (suc x m) y m
else True
例如: path 1 6 [(1,2),(2,3),(3,1),(5,4),(4,6)]
nevers结束
我以为我可以反转节点,所以左边的节点总是较小的节点,但我相信这是一个愚蠢的实现 . 提前致谢!
1 回答
我假设你的边缘列表描述了一般的有向图 . 第一个问题是你的
suc
函数只返回一个可能的后继函数,尽管通常会有多个 . 我们可以通过返回后继列表来解决这个问题:或者更短一些:
suc x = map snd . filter ((==x) . fst)
现在第二个问题是你想要实现一个depth-first search,但你没有把它弄得恰到好处:正如你所说的那样,你不能访问你已经访问过的节点 . 因此,您必须通过递归来携带已访问过的节点列表:
例: