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

備忘としてのメモを記載

幅 深さ

参考記事
JSで幅優先探索・深さ優先探索アルゴリズムを5行で実装してみた
深さ優先探索と幅優先探索の簡単な実装方法 - 働かないプログラマのメモ帳

//幅
const que = [targetNode];
while (que.length > 0) {
    const row = que.shift();
    if (row.children) row.children.forEach(childNode => que.push(childNode));
}

//深さ
const stack = [targetNode];
while (stack.length > 0) {
    const row = array.pop();
    if (row.children) row.children.forEach(childNode => stack.push(childNode));
}

キャッシュの先頭から取り出して子を後ろに追加すると幅優先
キャッシュの後ろから取り出して子を後ろ追加すると深さ優先

一覧表示するだけならこれでできるからシンプル。
ただ経路を表示したり、終了条件を追加してくとごちゃごちゃしてくる。

幅も再帰で作ろうかなと思ったけど、再帰って基本スタックだからキュー使おうとするとめんどくさくなっちゃった