[グラフ] 深さ優先探索をPythonで実装
Python で深さ優先探索を実装します。 ノードクラス 幅優先探索と同じです。 各ノードは自身の名前、隣接リスト、訪問済みかどうかのフラグを持ちます。 class Node(object): def __init__(s...
「DFS」一覧
[グラフ] 深さ優先探索
深さ優先探索 深さ優先探索（ふかさゆうせんたんさく、英:depth-first search, DFS、バックトラック法ともいう）は、木やグラフを探索するためのアルゴリズムである。アルゴリズムは根から(グラフの場合はどのノードを根にするか決定する)始ま...
[Python] ABC015 C メモ化再帰
この問題ではメモ化再帰を使う必要はないのですが、前述の問題を、練習のためメモ化再帰を使って解きなおします。 問題 C - 高橋くんのバグ探し 回答 defaultdict defaultdict をメモに使ってみます。 .fo...
[Python] DFSによるグラフの探索
無向グラフをDFSで探索するアルゴリズムを Python で記述します。 グラフは隣接リストを用いて表現します。 深さ優先探索 深さ優先探索（ふかさゆうせんたんさく、英: depth-first search, DFS、バックトラック法ともいう）...