:PROPERTIES: :ID: 82a1511c-0755-4bea-92c4-7e76dd84c646 :mtime: 20231027021556 :ctime: 20231027021555 :END: #+title: breadth-first search #+filetags: :public:project: * Implementations of BFS ** BFS in Ocaml *** BFS in [[id:8952459c-5076-4e68-8a68-5f658209f39e][Ocaml]] using [[id:cf967e5c-c8fd-4fd3-b333-e7c26925dca4][Ocaml Lists]] #+BEGIN_SRC ocaml type 'a tree = | Lf | Br of 'a * 'a tree * 'a tree #+END_SRC #+RESULTS: : type 'a tree = Lf | Br of 'a * 'a tree * 'a tree #+BEGIN_SRC ocaml let rec nbreadth = function | [] -> [] | Lf :: ts -> nbreadth ts | Br (v , l , r) :: ts -> v :: nbreadth (ts @ [l ; r]) let bfs t = nbreadth [t] #+END_SRC #+RESULTS: : <fun> #+BEGIN_SRC ocaml bfs (Br (1 , Br(2 , Br (5 , Lf , Br(7 , Lf , Lf)) , Lf) , Br(3 , Lf , Br(9 , Lf , Lf)) )) #+END_SRC #+RESULTS: | 1 | 2 | 3 | 5 | 9 | 7 | *** BFS in [[id:8952459c-5076-4e68-8a68-5f658209f39e][Ocaml]] using [[id:f1e2ca96-3b11-4d6a-bbe2-297f1bf45213][queue (computer science)]] #+BEGIN_SRC ocaml let rec qbreadth q = if (queue_null q) then [] else (let dq = (queue_pop q) in match (queue_head q) with | Lf -> (qbreadth dq) | Br (v , left, right) -> v :: qbreadth (queue_append (queue_append dq left) right)) let qbfs t = qbreadth (queue_append (empty_queue) t) #+END_SRC #+RESULTS: : <fun> #+BEGIN_SRC ocaml :exports both qbfs (Br (1 , Br(2 , Br (5 , Lf , Br(7 , Lf , Lf)) , Lf) , Br(3 , Lf , Br(9 , Lf , Lf)) )) #+END_SRC #+RESULTS: | 1 | 2 | 3 | 5 | 9 | 7 | * Benefits of BFS - Can do iterative deepening - Can work on infinite lazy trees