Genişlik-ilk ile derinlik-ilk arama arasındaki girdi/çıktı

Question

Soruma soru sorma, arama türünün mekanizmasıyla ilgili değil. Bunun kendisinden çok daha sıradan olduğunu hissediyorum - Ben de giriş ve çıkış anlamıyorum. Daha spesifik olarak, CLRS'de BFS girdi olarak bir grafik ve bir kaynak düğümü alır, ancak DFS sadece bir grafik alır. DFS o zaman aradığınız yerde ilgilenmiyor mu?

Girdi karmaşası budur. Çıktı karmaşası, DFS'de, işiniz bittiğinde, her bir düğümün keşfini ve bitiş zamanını kaydeden masaya benzer bir yapıya sahip olmanızdır, doğru mu? Bir çözümü, yani kaynaktan kaynaktan hedef düğümlere giden bir yolu nasıl çıkarırsınız?

Umarım mantıklı olurum. Teşekkürler!

Düzenleme: Burada, DFS tarafından bir kaynak düğümü kullanılmadığı kastediyorum. Bu, CLRS'den gelen DFS pseudocode'dur. Her yerde bir kaynak düğümü görmüyorum. Tek yaptığım şey, grafikteki tüm düğümlerden geçiyor.

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

giriş karışıklık: CLRS tarafından verilen

özellikle DFS sizden nerede arama umursamıyor. Aramanın kesin sonucu, V[G]'daki düğümlerin sırasına bağlı olacaktır. Bunun yerine, muhtemelen kendi amaca uygun tek bir ağaç, CLRS sürümü bir orman (grafiğin her bir bileşeni için bir ağaç) üretir

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) 

: Normalde bir düğüm, örneğin başlangıç ​​malzemesi olarak DFS düşünür daha iyi.

çıktı karışıklık:

yolları zaman damgaları ile değil kaydedildi, ancak ebeveyn işaretçiler π tarafından edilir. Örneğin, v numaralı bir düğüm verildiğinde, yolu kök düğümüne şu şekilde yazdırabilirsiniz:

Print-Path-To-Root(v) 
1 while v ≠ Nil 
2 do print v 
3  v ← π[v] 

Answer 2

Hem BFS hem de DFS bir kaynak düğümü olarak giriş yapar.

DFS ile yol bulmaya çalışırken, yalnızca düğümünüzü bulduğunuzda durursunuz ve ardından yolu bulmak için yığını asıl düğüme kadar tamamlarsınız.