【メモ】グラフの探索方法

グラフの探索方法のメモです。

実装の詳細というよりも、概念のメモです。

幅優先探索

1.キューに入れる(add)。訪問済にする。
2.キューが空でない限りループする
2-1.キューから取り出す(remove)。
2-2.隣接ノードに訪問する。未訪問の場合のみ、キューに入れる。訪問済にする。

深さ優先探索

スタックによる実装

1.スタックに入れる(push)。訪問済にする。
2.スタックが空でない限りループする
2-1.スタックから取り出す。
2-2.隣接ノードが

⇒なかった場合、またはノードが全て訪問済だった場合
　スタックから中身を取り出す(pop)。

⇒あった場合、かつノードが未訪問だった場合
　スタックに入れる。訪問済にする。
　直前にスタックに入れたデータに立ち寄る。

再帰による実装

省略