广度优先搜索Haskell

Question

图形定义如下:[("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)

但是当我运行它时,我得到了exeption: Exception:D:\ Workspace\Labwork2\src\Main.hs:(190,1) - (197,49):函数搜索中的非详尽模式

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

Answer 1

例外情况表明,您的模式并非详尽无遗.具体来说,您有以下模式search:

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

如果第一个参数是nil,则第四个参数也必须是,如果第一个参数不是nil,则第二个参数也必须不是nil.以下案例不包括在内:

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

您必须强制执行不变量以确保这些情况永远不会发生,或者您应该对它们采取合理的措施.

运行程序-Wall应该可以帮助您捕获诸如此类的非整体性问题.

(至于广度优先搜索:在Haskell中,如果你编写一个正确的图搜索,其中的结果不依赖于较低级别的结果,并且你不要求严格,那么它是否要求广度优先或深度 - 第一个或介于两者之间通常取决于结果的使用方式.)

(这是无关的,但是由空字符串标识的顶点真的有问题吗？如果你的图形实际上由空字符串标识了一个顶点怎么办？是否存在一个不变量,表明情况绝对不是这样？)