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) 查找，但最好使用图形库来完成您想要做的事情。