algorithm - 差分白黒訪問と探索 (dfs)

Question

最近、非再帰的な方法で dfs を実装しようとしました。ノードの探索とノードの訪問という2 つの別個の概念があるという事実に遭遇しました。違いは何ですか？

また、ノードが探索/訪問される順序を追跡している場合、それぞれの順序は何を表していますか?

Answer 1

違いはありません。深さ優先検索では、各ノードを 1 回だけ訪問します。別の用語として「探索」を使用する人もいると思いますが、実際には「訪問」の方が正確です。DFS がノードを訪問する順序は正確に定義されていません。現在のノードの子が複数ある場合、それらを任意の順序で再帰することができ、各順序ですべてのノードを訪問する順序が異なります。ただし、子の順序を定義している場合 (たとえば、グラフを近傍リストに保存している場合)、この順序で子を参照する方が自然です。