depth-first-search - 擬似コードでの深さ優先探索アルゴリズムのバックトラッキング

Question

boolean backtrackDFS(v)  {
   If  (SolutionFound(v))  return true;
   Mark vertex v as reached.
   for (each unreached vertex u adjacenct from v)
        if (backtrakDFS(u)) return true;
   Unmark vertex v; 
   return false;
}

ここでなぜUnmark vertex v必要なのですか？そして、なぜvが再び到達できなくなるような行を追加しても安全なのですか？それは再訪につながるのでしょうか？

Answer 1

必要ないと思います。通常は、自分が行ったことを元に戻し、見つけたときの状態のままにしておくことをお勧めします。

たとえば、その行を含めると、マークをクリアするための個別の操作なしで、同じ関数を複数回使用して検索できます。