Haskell中DFS的实现

Question

我已经苦思冥想了几个小时，因为我不知道如何在Haskell中编写深度优先搜索算法。

我的图是用邻接表实现的，其中键（或图的节点名称）是列表索引：

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

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

以下是DFS的代码示例：

以下是我目前为止编写的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

我理解问题在于当搜索到了图的一端后，它没有进行回溯并尝试其他相邻节点。为了解决这个问题，我一直在尝试修改守卫条件中的"otherwise"部分，但是似乎没有找到可行的方法。请问有什么方法可以解决这个问题？

- Coding District

---

那个程序能够被编译吗？而且在最坏的情况下，!! 的复杂度为O(n)，因此你的DFS复杂度将会更大。 - Satvik

如果这不是作业的话，你可能想使用函数图库（fgl）。它看起来有很多模块，但实际上很容易使用。 - Dietrich Epp

这里并不足以构成一个答案，但你可以看一下这篇论文：“在Haskell中构建深度优先搜索算法”。链接为www.researchgate.net/publication/2252048_Structuring_Depth-First_Search_Algorithms_in_Haskell/file/50463523c7a64b12d4.pdf。虽然不太容易理解，但应该表现良好。稍后我会进行测试。 - kgadek

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

- Satvik

Answer 2

我能想到的最短的翻译

dfs current visited =
    foldl (\visited next -> if elem next visited then visited else dfs next visited)
           (visited ++ [current]) (graph !! current)

与 Python 相比：

def dfs(v, visited):
    visited.append(v)
    for u in graph[v]:
        if u not in visited:
            visited = dfs(u, visited)
    return visited

- theluckyemil