2016-04-29 118 views
5

我一直在做一個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") 
];; 

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

+3

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

+1

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

回答

2

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

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我幫助過。