Haskell中的图表示

Question

我选择用Haskell中的节点列表（例如n=[1,2,3,4]）和代表边缘的一对列表（例如m=[(1,2)，(2,3)]）来表示图。现在我需要确定图是否强连通。

我主要问题是如何找到图中两个节点之间的路径。我写了类似这样的代码：

-- 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时，它是有效的，但对于度数更大的节点，它并不总是有效。你能给我一些线索吗？

- anna-k

---

+1 是因为你明确说明了这是作业！让我们知道如何帮助你。 - MtnViewMark

一旦某个特定的答案帮助您成功解决了问题，选择它（点击投票数下方的勾选标记）是很正常的，这样Stack Overflow就知道问题已经解决了。这也向其他成员表示他们现在可以花时间回答其他问题了。 - MtnViewMark

Answer 1

以下是需要翻译的内容：

以下是一些需要自问的问题：

1. adjacent 3 2 [(1,2),(2,3)] 是否应该为 True？
2. 在图 [(1,2),(2,3),(1,4),(3,4)] 中，数字 1 有多少个后继节点？
3. 为什么 way 需要同时包含 x==y 和 adjacent x y ... 的情况？或者为什么不需要？
4. way 的递归步骤中，== False 测试是否真的能让你从更小的图 m 上进行递归？

通常情况下，您没有为顶级函数编写类型签名。这样做通常非常有启发性，并且可以更清晰地传达您的设计：

type Vertex = Int
type Edge = (Vertex, Vertex)
type Graph = [Edge]

adjacent :: Vertex -> Vertex -> Graph -> Bool
suc :: Vertex -> Graph -> Vertex
way :: Vertex -> Vertex -> Graph -> Bool

考虑一下这些类型是否合理，以及它们是否按照你对图的思考方式分解了问题。

你真正的目标是 "way" 函数吗？还是要确定图是否连通？你可能对确定图是否连通的方法有过多的假设。

最后，关于 Haskell 语法的一小部分：与大多数其他语言一样，函数应用绑定非常紧密，比"=="和 "&&" 运算符更紧密。与大多数其他语言不同，函数应用不使用括号。因此， "adjacent" 可以重新编码为:

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

这可以进一步简化为：

adjacent x y [] = False
adjacent x y (mu:m) = (x == fst mu && y == snd mu) || adjacent x y m 

- MtnViewMark

---

谢谢您的评论，非常欢迎。我已经进行了修改，现在它可以正常工作了！ - anna-k

Answer 2

您有两个误解：

1.在整个搜索过程中，您的边缘列表`m`是静态的。不要在`way`中递归时使用它。

2.每个顶点可以有多条离开它的边。您想知道x的任何邻居是否有到y的路径。要查找邻居，您首先必须将边缘列表筛选为仅查找离开x的边缘。

您还需要建立一个已经访问过的节点列表，以便在寻找连接的过程中遇到已经访问过的节点时，该路径失败。

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

- Nathan Shively-Sanders