幅最初と深さfirst検索の入力/出力

Question

私の質問は、どちらの検索タイプのメカニズムに関するものではありません。それはそれよりもはるかにありふれたものだと思います - どちらの入力と出力も理解していません。より具体的には、CLRSでは、BFSは入力としてグラフとソースノードを入力しますが、DFSはグラフのみを取得します。 DFSは、それからどこで検索するか気にしませんか？

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

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

編集：DFSがソースノードを取得していないという意味です。これは、CLRSのDFS Pseudocodeです。ソースノードをどこにでも使用しているのはわかりません。私が見ているのは、グラフ内のすべてのノードを通過することです。

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

Answer 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]

Answer 2

BFSとDFSの両方がソースノードを入力します。

DFSでパスファインディングを行うときは、ノードを見つけたときに停止し、元のノードまでスタックしてパスを見つけます。