1

私の質問は、どちらの検索タイプのメカニズムについても実際にはありません。それよりもずっと平凡だと思います。どちらの入力と出力もわかりません。より具体的には、CLRSでは、BFSは入力としてグラフとソースノードを取りますが、DFSはグラフのみを取ります。それ以降、DFSはどこを検索してもかまいませんか？

これが入力の混乱です。出力の混乱は、DFSでは、完了すると、各ノードの検出と終了時間を記録するテーブルのような構造になっているということです。そこからソリューション、つまりソースノードから宛先ノードへのパスをどのように抽出しますか？

私は理にかなっていると思います。ありがとう！

編集：これが、DFSがソースノードを取得しないという意味です。これはCLRSからのDFS擬似コードです。私はそれがどこにもソースノードを取っているのを見ません。私が見ているのは、グラフ内のすべてのノードを通過することだけです。

DFS(G)
1 for each vertex u ∈ V[G]
2 do color[u] ← WHITE
3 π[u]← NIL
4 time ← 0
5 for each vertex u ∈ V[G]
6 do if color[u] = WHITE
7 then DFS-VISIT(u)

DFS-VISIT(u)
1 color[u] ← GRAY ✄ White vertex u has just been discovered.
2 time ← time+1
3 d[u] ← time
4 for each v ∈ Adj[u] ✄ Explore edge (u,v).
5 do if color[v] = WHITE
6 then π[v] ← u
7 DFS-VISIT(v)
8 color[u] ← BLACK ✄ Blacken u;it is finished.
9 f [u] ← time ← time+1
4

2 に答える 2

1

入力の混乱：

CLRSによって提供される特定のDFSは、どこから検索するかを気にしません。検索の正確な結果は、のノードの順序によって異なりますV[G]。通常、DFSはノードから開始すると考えます。例：

DFS-Simple(G, s)
1 for each vertex u ∈ V[G]
2   do color[u] ← WHITE
3 π[u]← NIL
4 time ← 0
5 DFS-VISIT(s)

CLRSのバージョンは、単一のツリーではなく、フォレスト（グラフのコンポーネントごとに1つのツリー）を生成します。これは、おそらくその目的により適しています。

出力の混乱：

パスは、タイムスタンプではなく、親ポインタによって記録されますπ。たとえば、ノードが与えられた場合v、次のようにルートノードへのパスを出力できます。

Print-Path-To-Root(v)
1 while v ≠ Nil
2   do print v
3      v ← π[v]
于 2010-11-19T19:24:01.067 に答える
0

BFSとDFSはどちらも、入力としてソースノードを取ります。

DFSを使用してパスファインディングを実行する場合は、ノードが見つかったら停止し、元のノードまでスタックを処理してパスを見つけます。

于 2010-11-18T15:17:58.537 に答える