院卒新人サラリーマンのメモ代わり

備忘としてのメモを記載

深さ優先探索

お気楽 OCaml プログラミング入門

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って状態を伴うから再帰にする必要がない気がしてきて、とりあえず後回し。