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

備忘としてのメモを記載

深さ優先

探索を中断する条件も追加してみた。
(ナイト巡回問題でいう一度行ったとこが含まれてたらダメみたいな条件)
getNextNodeのとこにisSuspendをうまく混ぜられたらいいなと思ったけど、難しそうだったのでとりあえずこれで

let dep = lst => {
    let isFinished = 終了条件
    let getNextNode = 次のノードリスト
    let isSuspend = 中断条件

    let aux = (linkedNode, acc) => {
        if (isFinished(acc)) return [acc]
        return linkedNode
            .map(curNode =>
                isSuspend(curNode,linkedNode) ?
                    []: aux(getNextNode(curNode, linkedNode), [curNode, ...acc]))
            .reduce((acc, cur) => acc.concat(cur),[])
    }

    return aux(lst, [])
}

isFInishedにtarget
getNextNodeにleftとrightいれれば木構造もほぼこのまま探索できそう