haskell - Haskell 中的 DFS 实现

Question

我已经绞尽脑汁几个小时了，因为我不知道如何在 Haskell 中编写 DFS..

我的图是作为邻接列表实现的，其中键(或图的节点名称)是列表索引:

0 -> 1
1 -> 0, 2
2 -> 1

As a Haskell list: [[1],[0,2],[1]]

这是迄今为止我的 DFS 代码:

dfs graph visited node = helper graph visited (graph !! node) node
    where helper _ _ visited [] _ = visited
          helper graph visited (x:xs) currNode
            | elem x visited = helper graph visited xs currNode
            | otherwise = dfs graph (currNode:visited) x

我知道问题在于，一旦到达图的一端，它就不会回溯并尝试另一个相邻节点。我一直在尝试修改守卫的其他部分以尝试修复它，但似乎无法想出有效的方法。我可以做什么来解决这个问题？

Answer 1

我仍然不太清楚你想要做什么。我写过和你类似的东西，虽然它有同样的问题 !! 不是 O(1)，但它仍然是 dfs。

mydfs graph visited [] = reverse visited
mydfs graph visited (x:xs) | elem x visited = mydfs graph visited xs
                           | otherwise = mydfs graph (x:visited) ((graph !! x) ++ xs)

dfs 回溯的想法是保留一个待访问列表，只需从中取出第一个条目并访问它，每当发现未访问的条目时，将其相邻顶点推到待访问列表的顶部。

您可以使用数组或向量作为邻接列表以避免 O(n) 查找，但最好使用图形库来完成您想要做的事情。