ocaml圖遍歷：如何保存訪問節點？

Question

我在試圖用DFS遍歷一個圖。

但是，當我試圖通過訪問節點列表作爲函數的參數，我發現有一個問題。

當我具備除了其前一個節點沒有連接的節點，遞歸調用結束，有關訪問節點消失，所以陷入無限循環的信息的節點達到...

是否有任何的方式來保持關於訪問節點的信息，除了使用命令的方式？

Answer 1

詳細闡述Jeffrey的答案，你有幾種不同的風格可用。我在這裏只給出了我沒有測試過的片段，所以可能會有小的或大的錯誤。

1. 您可以在任何地方使用的副作用：

   module NodeSet = Set.Make(...) 
   
   let traverse action graph_root = 
       let visited = ref NodeSet.empty in 
       let rec loop node = 
       action node; 
       visited := NodeSet.add node !visited; 
       let handle child = 
        if not (NodeSet.mem child !visited) 
        then loop acc child in 
       List.iter handle (children node) 
       in loop graph_root 
   

   的「拜訪」勢在必行功能action適用於 圖中的所有節點。

2. 可以遍歷的狀態存儲在一個可變的引用被訪問的節點，但是螺紋 作爲直接的累加器acc代替 測序副作用。這將對應於國家monad的使用 。

   let traverse action init_state graph_root = 
       let visited = ref NodeSet.empty in 
       let rec loop acc node = 
       let acc = action acc node in 
       visited := NodeSet.add node !visited; 
       let handle acc child = 
        if NodeSet.mem child !visited 
        then acc 
        else loop acc child in 
       List.fold_left handle acc (children node) 
       in loop init_state graph_root 
   

3. 您可以重複這種狀態下，通過邏輯還通過走訪 節點的信息。

   let traverse action init_state graph_root = 
       let rec loop acc visited node = 
       let acc = action acc node in 
       let visited = NodeSet.add node visited in 
       let handle (acc, visited) child = 
        if NodeSet.mem child !visited 
        then (acc, visited) 
        else loop acc visited child in 
       List.fold_left handle (acc, visited) (children node) 
       in loop init_state NodeSet.empty graph_root 
   

4. 最後，你可以通過 有關哪些節點應該在第一 遞歸調用計算旁邊移動到尾遞歸遍歷。這對應於繼續傳遞樣式的一般轉換，但是具有繼續的域特定表示 （僅僅是要訪問的節點）。

   let traverse action init_state graph_root = 
       let rec loop acc visited = function 
       | [] -> acc 
       | node::to_visit -> 
        if NodeSet.mem node visited then loop acc visited to_visit 
        else begin 
        let acc = action acc node in 
        let visited = NodeSet.add node visited in 
        let to_visit = children node @ to_visit in 
        loop acc visited to_visit 
        end 
       in loop NodeSet.empty init_state [graph_root] 
   

   傑弗裏的言論，與此演示文稿，可以在 遍歷順序從DFS通過簡單地改變着to_visit 更新更改爲BFS，添加子節點的序列的末端，而 比年初（這需要在算法上有效的隊列結構爲 ）。

Answer 2

看看這個的一種方法是，你想要轉發來嘗試圖中其他可能的節點，而不是返回（就像你會這樣做，例如遍歷一棵樹）。您可以使用參數來描述您訪問過的節點，但您計劃訪問的節點。訪問參數最初只是第一個節點。每次到達新節點時，都會將所有未訪問的相鄰節點（通過查看訪問節點集可以看出）添加到未訪問節點集，並以遞歸方式繼續。然後，DFS和BFS之間的區別就在於您對要訪問的節點列表進行排序。

在函數式編程中，有許多次不是從函數返回時，而是調用函數來做下一件事。 （這就是爲什麼尾遞歸有時很重要。）