在Haskell

我一直在敲打我的頭在牆上的幾個小時DFS實現，因爲我無法弄清楚如何在Haskell寫DFS ..在Haskell

My圖表實現爲鄰接表，其中鍵（或圖表的節點名稱）的列表索引：

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

我明白，問題是，它不會走回頭路，嘗試另一種相鄰節點一旦到達圖的一端。我一直在試圖修改警衛的其他部分，試圖解決它，但似乎無法提出一些有用的東西。我能做些什麼來解決這個問題？

來源

2012-10-05 Coding District

難道連編譯？在最壞的情況下，'!!'的複雜度是O（n），所以你的dfs的複雜度會更大。 – Satvik

如果這不是家庭作業，您可能需要使用功能圖庫（fgl）。它看起來令人望而生畏，但它實際上很容易使用。 –

這對於答案來說太少了，但看看這篇文章：「在Haskell中構建深度優先搜索算法」www.researchgate.net/publication/2252048_Structuring_Depth-First_Search_Algorithms_in_Haskell/file/50463523c7a64b12d4.pdf - 這不是最容易掌握的但是......好的，應該表現良好。我稍後會做測試。 – kgadek

你想要做的事情對我來說還不是很清楚。我寫了類似於你的東西，雖然它有相同的問題，!!不是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列表，並就掏出從它的第一項和訪問它，每當你發現沒有訪問推動頂部與其相鄰頂點的條目有目共睹的名單。

可以將數組或向量用於鄰接列表以避免O（n）查找，但最好使用圖庫作爲您正在嘗試執行的操作。

來源

2012-10-05 04:17:19 Satvik

最短我能想出

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

比較蟒蛇：

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-09 20:11:18 theluckyemil

回答

相關問題