小编Maz*_*ong的帖子

最近,我已经从Stackoverflow中的Graph中提出了构建DFS树的问题,并且已经了解到可以使用State Monad简单地实现它.

在haskell的DFS

虽然DFS要求仅跟踪被访问节点,因此我们可以使用"Set"或"List"或某种线性数据结构来跟踪被访问节点,BFS需要完成"被访问节点"和"队列"数据结构.

我的BFS伪代码是

Q = empty queue
T = empty Tree
mark all nodes except u as unvisited
while Q is nonempty do
u = deq(Q)
    for each vertex v ? Adj(u)
        if v is not visited 
        then add edge (u,v) to T
             Mark v as visited and enq(v)

从伪代码可以推断,我们每次迭代只需要做3个进程.

1. 从队列中出列点
2. 将点的所有未访问的邻居添加到当前树的子节点,队列和"已访问"列表
3. 在队列中重复此操作

由于我们没有使用递归遍历进行BFS搜索,我们需要一些其他的遍历方法,例如while循环.我在hackage中查找了loop-while包,但似乎有点弃用了.

我假设我需要这样的代码:

{-...-}
... =   evalState (bfs) ((Set.singleton start),[start])
where 
    neighbors x = Map.findWithDefault [] x adj 
    bfs =do (vis,x:queue)<-get
             map (\neighbor ->
                  if (Set.member …

我试图使用递归算法构造DFS树.

伪代码是:

DFF(G)
Mark all nodes u as unvisited
while there is an unvisited node u do 
    DFS(u)

.

DFS(u)
Mark u as visited
for each v in u's neighbor do 
    if v is not marked
        DFS(v)

虽然我可以通过为un/visited节点构建某种数据结构,以简单的方式在命令式语言中轻松实现这一点,为Haskell分配动态分配或某种声明,但由于Haskell的纯粹性阻止了我,所以不可能这样做传递参数时更改数据.

data Graph a = Graph [(a,[a])] deriving (Ord, Eq, Show)
data Tree a = Node a [Tree a] deriving (Ord, Eq, Show)

type Point = (Int, Int)
type Edges = [Point]
type Path = [Point]

pathGraphFy :: Graph Point -> Point -> …