OCAML深度優先搜索

我一直在做一個OCaml的教程（不要問我爲什麼，我只是決定擴大我的語言知識，我猜），我已經到了我所處的位置與圖表一起工作。該教程教會了我如何在圖形上進行廣度優先搜索，這可以很好地實現。然而，我一直在努力尋找深度優先搜索的算法，這是本教程的其中一個方面，「我們建議您使用深度優先方法來嘗試，但我們不會告訴您如何做吧。「OCAML深度優先搜索

我試圖執行它像這樣：let rec dfs graph start end。也就是說，我一直試圖在邊界列表（），起始節點（start）和結束節點（end）中進行。

我用邊的列表中創建我的圖...

let edges = [ 
    ("a", "b"); ("a", "c"); 
    ("a", "d"); ("b", "e"); 
    ("c", "f"); ("d", "e"); 
    ("e", "f"); ("e", "g") 
];;

不過，我完全失去了到哪裏何去何從。有關如何讓我走的任何建議？謝謝。

來源

2016-04-29 jpabene

通常的一句話總結是，深度優先搜索與廣度優先搜索相同，只不過您用堆棧替換未訪問節點的隊列。您可以嘗試以這種方式修改您的廣度優先搜索實現。 –

用於列出節點後繼的函數可能會讓您更容易。 – PatJ

所以，我做到了，但我覺得很奇怪，如果您必須在其中搜索，則將圖表表示爲列表。地圖會好很多。總之，這裏的它是如何做：

let edges = [ 
    ("a", "b"); ("a", "c"); 
    ("a", "d"); ("b", "e"); 
    ("c", "f"); ("d", "e"); 
    ("e", "f"); ("e", "g") 
];; 

let successors n e = 
    List.map (fun (_, v) -> v) (List.filter (fun (u, _) -> n = u) e) 

let dfs graph start f = 
    let rec rdfs visited node = 
    if not (List.mem node visited) then 
     begin 
     f node; 
     let s = successors node graph in 
     List.fold_left rdfs (node::visited) s 
     end 
    else visited 
    in rdfs [] start 

let() = let _ = dfs edges "a" print_string in()

第一件事就是定義一個successors功能，這將給你一個節點的每一個直接繼承（在List.filter部分讓你邊時，List.map部分兩個部分所產生的邊緣分裂並且只保留第二個（第一個是你正在搜索後繼的節點）

dfs函數定義了一個內部函數，它執行兩件事，檢查我們正在處理的節點是否已經訪問或不是。

如果是，沒有任何變化，我們只是返回相同的訪問節點列表（也許還有一些其他的事情取決於你想要做的搜索）。
如果沒有，那麼
- 我們申請，我們給了dfs當前節點的功能，
- 我們添加此節點到訪問節點，
- 我們把他的繼任者，
- 我們把這個功能應用到每一個，（這裏有一個小竅門，因爲我們有
  
  List.fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a
  
  和
  
  rdfs : string list -> string -> string list
  
  ，而不是寫
  
  List.fold_left (fun visited node -> rdfs visited node) ...
  
  我們可以寫
  
  List.fold_left rdfs ...
  
  （事做這個所謂的演算和一些奇怪的事情規則稱爲ETA轉換其中指出：
  
  λ x · ux η u (x ∉ fv(u))（fv(u)是U的自由變量）:-P）（這是什麼意思，如果在OCaml中，如果你寫fun x -> f x你可以有寫f相反，它是完全等同。）
- 回到其所有訪問節點都被添加的訪問節點列表

^h我幫助過。

來源

2016-06-10 00:35:05 Lhooq

OCAML深度優先搜索

回答

相關問題