Haskell中的图形表示

我选择用节点列表（例如n=[1,2,3,4]）和表示边缘的对列表（示例m=[(1,2), (2,3)]）在Haskell中表示图形。现在我必须看看图表是否强连接。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度节点，但对于具有更大程度的节点并不总是工作。你能给我一些线索吗？

来源

2010-05-05 anna-k

+1为是明确它是家庭作业！让我们知道如何接近帮助。 – MtnViewMark 2010-05-05 20:28:59

一旦某个特定答案帮助您成功解决了您的问题，选择它就很正常（点击投票计数下的复选标记），以便知道问题已解决。向成员表明他们现在可能想花时间处理其他问题。 – MtnViewMark 2010-05-06 13:13:18

你必须了解两个错误：

m，您边缘的名单是在整个搜索静态的。当你在way中再次发生时，不要吃它。
每个顶点可以有多于一个的边缘。你想知道x的邻居any是否有y为way。要找到您首先需要的邻居filter边缘列表才能找到只留下x的边。

您还需要建立一个您已经访问过的节点列表，以查找连接。如果你最终在一个你已经看到的节点上，那么这条特定路径失败了。

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

来源

2010-05-05 20:22:05

这里有一些问题要问自己：

应该adjacent 3 2 [(1,2),(2,3)]是True？
多少接班人1图中的[(1,2),(2,3),(1,4),(3,4)]
为什么有呢，还是没有，way需要同时拥有x==y情况和adjacent x y ...情况？
在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

来源

2010-05-05 20:26:05 MtnViewMark

感谢您的意见，他们欢迎。我已修改，现在它的作品！ – 2010-05-06 12:49:36

Haskell中的图形表示

回答

相关问题