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

私が思いつくことができる最短

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 に答える
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 がバックトラックするためのアイデアは、tobevisited のリストを保持し、そこから最初のエントリを取り出してアクセスし、アクセスされていないエントリを見つけるたびに、隣接する頂点を tobevisited リストの上にプッシュすることです。

隣接リストに配列またはベクトルを使用して O(n) ルックアップを回避できますが、目的にはグラフ ライブラリを使用することをお勧めします。

于 2012-10-05T04:17:19.597 に答える