广度优先搜索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：异常:函数搜索中的非穷举模式。

我的错误是什么?如果给出了我的图，如何实现宽度优先搜索？

Answer 1

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

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

如果第一个参数是零，第四个参数也必须是，如果第一个参数不是零，那么第二个参数也不能是零。下列情况未包括在内：

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

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

通过-Wall运行您的程序可以帮助您捕捉非全局性问题，如这些问题。

(至于广度优先搜索:在Haskell中，如果你写了一个正确的图搜索，如果你的搜索结果不依赖于低级的结果，也不需要严格的要求，那么宽度优先还是深度优先通常取决于结果的使用方式。)

(这是不相关的，但是有一个由空字符串标识的顶点真的是个问题吗？如果图中有一个由空字符串实际标识的顶点，该怎么办？是否存在一个不变量，说明从来没有这种情况？)

Answer 2

你没有理由

search [item] [] _ _ _

很明显你的程序在处理这个案子。您是否有一个不变式，说明如果图是空的，那么开始符号就会耗尽？