デプスファーストサーチはノードにどのようにアクセスしますか？

Question

アルゴリズムはノードに2回目に来ることがあり、すなわち、ノードへの2つの経路が存在する可能性がある。アルゴリズムはどのパスがより短いかを知る必要があります。

ベスト・ファースト・サーチが以前に訪れたノードに到達すると、以前の訪問がより長いパスを持つ可能性があります。これが起こると、開いているリストと閉じたリストを更新する必要があります。 これはA *検索では発生しません。

質問：これはDFSで起こりますか？

答えははいですが、私はそれがノーだと思いました。なぜそれははいですか？私はノードが訪問されたら、それに戻らないと思った。

Answer 1

DFS戦略は、ノードへのパスを検出する回数だけノードを訪問します。そのノードからその訪問を継続することはありませんが、訪問自体を登録します。これはDFS edge classificationに不可欠です。

たとえば、このグラフ上でDFSを実行することを検討：

はじめてのノードCに到達すると、パスはA-B-Cです。 2回目にCに到達すると、パスはA-Cになります。

Answer 2

あなたはこの

A 
|\ 
B \ 
| E 
C/
|/ 
D 

のようなグラフがあり、左から右へ、深さ優先、それを通過する場合は、以下のpathesの順で訪問されます。

A 
AB 
ABC 
ABCD 
AE 
AED 

あなたが見ます、 Dの最初の訪問は、2番目の訪問（AED）より長い経路（ABCD）にあります。