7

由于我不知道如何在 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

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

4

2 回答 2

2

你想要做什么对我来说仍然不是很清楚。我写了一些与你类似的东西，虽然它有同样的问题，!!不是 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) 查找，但最好将图形库用于您正在尝试做的事情。

于 2012-10-05T04:17:19.597 回答
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
于 2016-11-09T20:11:18.563 回答