几个小时，我正在尝试实现Haskell的深度优先搜索。我的depthfirst算法给出了一个起始节点和一个图。这就是我到目前为止+图数据类型的定义。
data Graph a = G [a] (BRfun a)
有：
type BRfun a = a -> [a]
目前的尝试：
depthFirst :: Eq a => a -> Graph a -> [a]
depthFirst a (G [a] sucs) = [a]
因此，如果节点列表中只有一个元素是我必须放在最终列表中的唯一元素（我认为应该是取消条件）。但现在我正在努力创建一个递归算法来首先获得最深的节点。
对于像DFS和BFS这样的图形搜索，您需要保留先前访问过的顶点列表。这样就可以检查你之前是否看过一个顶点，这样你就不会访问一个顶点两次（这也会处理周期，虽然它实际上无法检测周期是否存在）。
这是我的实施。 visited列表记录了访问过的顶点。对于我们遇到的每个顶点，我们通过遍历列表来检查它是否已被访问过。当我们“访问”一个顶点（即在else分支中）时，我们将顶点添加到列表中。访问列表通过在foldl中传递来保持最新。
在这种方法中，我们实际上可以劫持visited列表以记录深度优先顺序。由于我们在第一次看到它们时将顶点添加到列表中，因此visited列表的反向深度优先顺序。所以我们只需在搜索完成后撤消它。
depthFirst source (G _ sucs) = reverse (search [] source)
where
search visited v =
if v `elem` visited
then visited -- already seen v, so skip it
else foldl search (v:visited) (sucs v)
我建议逐步了解代码如何在小图上执行，以了解代码的工作原理以及代码的正确性。例如，从源0开始，按照以下定义的图表进行尝试。
edges = [[1,2,3],[4],[5],[4,6],[5],[1],[4]]
g = G [0,1,2,3,4,5,6] (edges!!)
最后，请注意，此实现是正确的但效率非常低，为n个顶点和m个边的图形花费时间O（nm），因为我们遍历每个边的访问列表一次。在一个更有效的实现中，您可能希望保留两个数据结构，一个用于查找是否已访问过顶点（例如哈希集或二进制搜索树），另一个用于查找深度优先排序。
我喝了太多酒，对我所谈论的内容有点模糊，但这是我提出的解决方案。
depthFirst :: Eq a => a -> Graph a -> [a]
depthFirst root (G _nodes edges)
= reverse $ go [] root
where
go seen x
| x `elem` seen = seen
| otherwise = foldl' go (x:seen) (edges x)
我在这里使用来自foldl'的Data.List，因为我们想要从左到右遍历节点，这对foldr来说有些挑战。直接使用没有foldl的'通常不是一个好主意，因为除非强迫（强迫正是foldl'所做的），它会建立thunks。
因此，正如我在评论中所概述的那样，总体思路如下。在第一次机会下到树下，保持你沿途看到的节点列表。如果一个节点没有传出边缘，很酷，你就完成了。如果你已经看过一个给定的节点，保释，你不需要无限递归。
折叠从当前节点开始，前面是已经看过的节点列表（在开头，空列表）。然后，从左到右，它访问从当前节点直接可到达的每个节点。在每个“下一个”节点，它构建子树的反向深度优先顺序加上已经看过的节点。已经看到的节点被转移到每个“下一个”节点（从左到右的顺序）。如果没有可从当前节点到达的节点，则它仅返回所有看到的节点列表前面的当前节点。
看到的节点列表是相反的，因为前置是O(1)，而附加是O(n)。更容易扭转一次并获得复杂性O(n)而不是每次追加并获得大致O(n²)的复杂性（复杂性来自我的头顶，我不仅有点醉，所以应用盐自由）
如果elem x seen，函数bails返回到目前为止看到的所有节点的列表。它确保我们不会递归到我们已经访问过的节点，因此避免了循环图上的无限递归。
这是经典的深度优先搜索。它可以被优化，优化的潜力是相当明显的（对于一个，elem x seen有O(n)最坏情况的复杂性，而它可能是O(log n)。随意改进代码。
作为最后一点建议，Graph的类型不保证节点是唯一的。更严格的实现看起来像这样：data Graph a = G (Set a) (BRfun a)，其中Set来自Data.Set（或类似的东西）。鉴于列表中所述的定义，重新标记所有节点，f.ex可能是个好主意。 nodes' = zip [1..] nodes或类似的东西。