DFS algoritması Geçişi

Question

, bir yığın ile DFS geçişi bana folowing yolunu verir ...

1-2-3-4-5-6

mi Yukarıdaki yol geçerli mi? Başka bir yol var mı? (ders kitabım bana 1-2-3-6-4-5 verir)

Bilgisayar bilimi yığınında görüntüleri yayınlamak için yeterince temsilcisi yok, bu yüzden burada sormak için başvurmak zorunda kaldım, uygun olup olmadığından emin değilim ; eğer değilse, daha sonra silmek için mutluyum. Grafiğin mükemmel geçerli DFS geçişi listeledik ve ders kitabı size grafiğin başka tamamen yasal DFS geçişi veriyor

Answer 1

sayesinde. Aynı grafiğin birçok derinlikli ilk geçişi olabilir (aslında, çoğu kez üstel olarak çoğalır), dolayısıyla ders kitabınız ile aynı olanı alamazsanız, bunun sebebi alarma neden olmaz. hakkında bazı başka kurallar varsa nasıl düğümler sonra, bir DFS (örneğin, her zaman artan veya azalan sırayla bağlı düğümleri ziyaret) ziyaret gerektiğini,

1 2 5 4 3 6 
3 1 6 2 5 4 
5 4 2 3 1 6 
... 

Ancak: Burada

diğer bazı sıralamalar vardır Arama her zaman aynı çıktıyı üretecektir.

Bu yardımcı olur umarız!

Answer 2

Açıkladığınız çıktı bir yol değil, DFS'nin düğümleri ziyaret ettiği sıra. Bir yol, her düğümün bir önceki ve bir sonraki düğüme bağlandığı düğümlerin bir listesidir.

DFS kastetmek çıktısı da sizin durumunuzda karşılık gelen bir DFS geçişi ağacının olarak görülebilir

:

1 - 2 - 3 - 4 - 5 
     | 
     6 

ders kitabı ağaç

1 - 2 - 3 - 6 
     | 
     4 - 5 

Farklı birçok alabiliriz DFS ağaçları, çünkü seçim yapabileceğiniz her noktada, ilk önce nereye gideceğinize karar verebilirsiniz. Örneklerinizde, düğüm 3'ten düğüm 4 veya düğüm 6'ya gidebilir ve farklı çıktılar farklı seçeneklerden kaynaklanır.