0

图形定义如下：[("1",["2","3"]),("2",["1"]),("3",["1"])]

我想写一个广度优先搜索。

这是我的代码：

search_command graph start ""=(graph,"You didnt enter start vertex!\n")
search_command graph ""  end=(graph,"You didnt enter end vertex!\n")
search_command graph start end=
    if (has_element graph start)&&(has_element graph end) then 
            (graph,unwords (search graph [start] end [] []))
    else if (has_element graph end)==False then 
            (graph,"Element with "++end++" name not found!")
    else 
            (graph,"Element with "++start++" name not found!")


search [] _ _ [] result=result 
search (item:graph) (x:start) end use result=
    if (fst item==x)&&(elem x use)==False then
            search graph (get_connect_vertices graph graph (fst item) []) end (use++[x]) (result++[x])
    else if (fst item==end)&&(fst item==x) then
            search [] [] "" [] (result++[x]++[end])
    else
            search graph [x] end use (result)

但是当我运行它时，我得到了异常： 异常：D:\Workspace\Labwork2\src\Main.hs:(190,1)-(197,49): Non-exhaustive patterns in function search

我的错误是什么？如果按我的方式给出图表，如何实现广度优先搜索？

4

2 回答 2

5

正如例外所暗示的，您的模式并非详尽无遗。具体来说，您有以下模式search：

search []    _     _ [] _
search (_:_) (_:_) _ _  _

如果第一个参数是 nil，那么第四个参数也必须是，如果第一个参数不是 nil，那么第二个参数也一定不是 nil。以下情况不包括在内：

search [] _ _ (_:_) _
search (_:_) [] _ _ _

您必须强制执行不变量以确保这些情况永远不会发生，或者您应该对它们做一些合理的事情。

运行您的程序-Wall应该可以帮助您发现诸如此类的非全面性问题。

（至于广度优先搜索：在 Haskell 中，如果你编写了一个正确的图搜索，其中顶层结果不依赖于低层结果，并且你不要求严格，那么无论结果是广度优先还是深度 -首先或介于两者之间通常取决于结果的使用方式。）

（这是不相关的，但是有一个由空字符串标识的顶点真的是个问题吗？如果你的图有一个由空字符串实际标识的顶点怎么办？是否有一个不变量表明这种情况永远不会发生？）

于 2013-08-07T15:35:42.623 回答
3

你没有理由

search [item] [] _ _ _

显然，您的程序遇到了这种情况。您是否有一个不变量表明如果图表为空，则开始符号已用尽？

于 2013-08-07T15:31:43.663 回答