Veri Yapısı - Derinlik İlk Geçiş
Derinlik İlk Arama (DFS) algoritması, bir grafiği derinlemesine bir hareketle dolaşır ve herhangi bir yinelemede bir çıkmaz meydana geldiğinde, bir aramayı başlatmak için sonraki tepe noktasını almayı hatırlamak için bir yığın kullanır.
Yukarıda verilen örnekte olduğu gibi, DFS algoritması önce S'den A'ya D'den G'ye E'den B'ye, sonra F'ye ve son olarak C'ye geçer. Aşağıdaki kuralları kullanır.
Rule 1- Bitişikteki ziyaret edilmemiş köşeyi ziyaret edin. Ziyaret edildi olarak işaretleyin. Göster onu. Bir yığın halinde itin.
Rule 2- Bitişik köşe bulunamazsa, yığından bir tepe noktası açın. (Yığından bitişik köşeleri olmayan tüm köşeleri açacaktır.)
Rule 3 - Yığın boşalana kadar Kural 1 ve Kural 2'yi tekrarlayın.
| Adım | Geçiş | Açıklama |
|---|---|---|
| 1 |
|
Yığını başlatın. |
| 2 |
|
işaret Sziyaret edildiği gibi ve yığının üzerine koyun. Şuradan ziyaret edilmemiş herhangi bir bitişik düğümü keşfedinS. Üç düğümümüz var ve bunlardan herhangi birini seçebiliriz. Bu örnek için, düğümü alfabetik sıraya göre alacağız. |
| 3 |
|
işaret Aziyaret edildiği gibi ve yığının üzerine koyun. A'dan herhangi bir ziyaret edilmemiş bitişik düğümü keşfedin.S ve D bitişik A ancak yalnızca ziyaret edilmemiş düğümler için endişeliyiz. |
| 4 |
|
Ziyaret etmek Dve ziyaret edildi olarak işaretleyin ve yığına koyun. Burada biz varB ve C bitişik düğümler Dve ikisi de ziyaret edilmemiş. Ancak yine alfabetik sırayla seçeceğiz. |
| 5 |
|
Biz seciyoruz B, ziyaret edildi olarak işaretleyin ve yığına koyun. BurayaBziyaret edilmemiş bitişik düğümü yok. Bu yüzden patlıyoruzB yığından. |
| 6 |
|
Önceki düğüme dönmek için yığının tepesini kontrol ediyoruz ve ziyaret edilmemiş düğümler olup olmadığını kontrol ediyoruz. Burada buluyoruzD yığının tepesinde olmak. |
| 7 |
|
Yalnızca ziyaret edilmemiş bitişik düğüm D dır-dir Cşimdi. Bu yüzden ziyaret ediyoruzC, ziyaret edildi olarak işaretleyin ve yığına koyun. |
Gibi Cziyaret edilmemiş bitişik düğüme sahip değil, bu nedenle ziyaret edilmemiş bitişik düğümü olan bir düğüm bulana kadar yığını patlatmaya devam ediyoruz. Bu durumda, hiç yok ve yığın boşalana kadar patlamaya devam ediyoruz.
Bu algoritmanın C programlama dilinde uygulanmasını öğrenmek için burayı tıklayın .