深さ優先探索
let adjacent = [ [1, 2], /* A */ [0, 2, 3], /* B */ [0, 1, 4], /* C */ [1, 4, 5], /* D */ [2, 3, 6], /* E */ [3], /* F */ [1] /* G */ ]; let depth_first_search = (start, goal) => { let rec aux = pathList => { let curPos = List.hd(pathList); let curPath = List.nth(adjacent, curPos); switch (curPos == goal) { | true => [List.rev(pathList)] | _ => /* 現在地からつながっている場所でまだ行ってないとこを追加 */ curPath |> List.fold_left( (acc, el) => List.mem(el, pathList) ? acc : acc @ aux([el, ...pathList]), [], ) }; }; aux([start]); };
幅優先探索も再帰でやろうと思ったんだけどqueueって状態を伴うから再帰にする必要がない気がしてきて、とりあえず後回し。