haskell - Haskell中的图形表示

我选择用节点列表（例如n=[1,2,3,4]）和成对的边列表（例如m=[(1,2), (2,3)]）来表示Haskell中的图。现在，我必须查看该图是否牢固连接。

我的主要问题是如何找到图中2个节点之间是否有路。我写了这样的东西：

-- sees if 2 nodes are adjacent

adjacent x y [] = False

adjacent x y (mu:m) =
        if(x== (fst mu) && y==(snd mu)) then True
        else adjacent x y m

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

-- my main function
way 0 y list = False

way x y (mu:m)
    | x==y = True
    | (adjacent x y (mu:m)) == True = True
    | otherwise =
        if ((way (suc x (mu:m)) y (mu:m))==False) then way (suc x m) y m
        else True

当我有1级节点时，它可以工作，但对于度数较大的节点，它并不总是有效。你能给我一个线索吗？

最佳答案

您有两个理解上的错误：


m，您的边列表在整个搜索过程中都是静态的。当您在way中重复播放时，请不要吃饱了。
每个顶点可以有多个边缘。您想知道x的邻居的any是否与y的way。要查找邻居，您首先必须filter边列表仅查找离开x的边。


您还需要建立一个在寻求连接时已经访问过的节点的列表。如果最终到达已经看到的节点，则该特定路径已失败。

一些使您的代码更短的提示：对于adjacent，请尝试elem。
对于succ，请尝试Data.Maybe.fromMaybe和lookup。