Home Articles

Haskell的图形路径

Asked
Viewed 387 times
0

提供一个复制图形边缘列表的列表,我想在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 Answer

  • 1

    我假设你的边缘列表描述了一般的有向图 . 第一个问题是你的 suc 函数只返回一个可能的后继函数,尽管通常会有多个 . 我们可以通过返回后继列表来解决这个问题:

    suc :: Int -> [(Int,Int)] -> [Int]
    suc x [] = []
    suc x ((y,z):list) =
        if x == y then z : suc x list
        else suc x list
    

    或者更短一些: suc x = map snd . filter ((==x) . fst)

    现在第二个问题是你想要实现一个depth-first search,但你没有把它弄得恰到好处:正如你所说的那样,你不能访问你已经访问过的节点 . 因此,您必须通过递归来携带已访问过的节点列表:

    path :: Int -> Int -> [Int] -> [(Int,Int)] -> Bool
    path src dst visited edges
        | src == dst = True
        | src `elem` visited = False
        | otherwise = any (\nxt -> path nxt dst (src : visited) edges) (suc src edges)
    

    例:

    *Main> path 1 6 [] [(1,2),(2,3),(3,1),(5,4),(4,6)]
    False
    *Main> path 1 3 [] [(1,2),(2,3),(3,1),(5,4),(4,6)]
    True
    

Related