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 回答