Автор ikbal, 12 лет назад, По-английски
  • Проголосовать: нравится
  • +24
  • Проголосовать: не нравится

Автор _Eren_, 12 лет назад, По-английски

Depth First Search ( DFS )

DFS çizge'yi gezmenin yollarından biridir. DFS'nin mantığı şöyledir: gidebildiğin kadar git gidemiyorsan geri dön.

Algoritma

DFS'de her düğüm 3 farklı duruma sahip olabilir.

Beyaz : Düğüme ulaşılmamış.

Gri : Düğüm işleniyor.

Siyah : DFS düğümü işlemeyi bitirdi.

İlk olarak tüm düğümler beyaz. DFS bir kaynak düğümden başlar ve aşağıda gösterilen şekilde çalışır:

1. Düğüm u'yu gri olarak işaretle.
2. Her ( u , v ) kenarı için v beyaz ise DFS'yi v için özyinelemeli olarak çalıştır.
3. Düğüm u'yu siyah olarak işaretle ve geldiğin düğüme geri dön.

Aşağıdaki çizgeyi 1 numaralı düğümden başlayarak DFS'yi kullanarak gezelim.


Çizge.

 Düğüm 1'i gri olarak işaretle.

 (1 , 4) kenarı var ve düğüm 4 beyaz. Düğüm 4'e git.

 Düğüm 4'ü gri olarak işaretle.

 (4 , 2) kenarı var ve düğüm 2 beyaz. Düğüm 2'ye git.

 Düğüm 2'yi gri olarak işaretle.

 (2 , 5) kenarı var ve düğüm 5 beyaz. Düğüm 5'e git.

 Düğüm 5'i gri olarak işaretle.

 (5 , 3) kenarı var ve düğüm 3 beyaz. Düğüm 3'e git.

 Düğüm 3'ü gri olarak işaretle.

 Düğüm 3'ten gidilicek düğüm kalmadı. Düğüm 3'ü siyah olarak işaretle ve düğüm 5'e dön.

 (5 , 4) kenarı var ama düğüm 4 gri.

 Düğüm 5'ten gidilicek düğüm kalmadı. Düğüm 5'i siyah olarak işaretle ve düğüm 2'e dön.

 Düğüm 2'den gidilicek düğüm kalmadı. Düğüm 2'yi siyah olarak işaretle ve düğüm 4'e dön.

 (4 , 5) kenarı var ama düğüm 5 siyah.

 Düğüm 4'ten gidilicek düğüm kalmadı. Düğüm 4'ü siyah olarak işaretle ve düğüm 1'e dön.

 Düğüm 1'den gidilicek düğüm kalmadı. Düğüm 1'i siyah olarak işaretle ve DFS'yi sonlandır.

Örnekte görüldüğü gibi DFS tüm yollardan gitmez. DFS'nin kullanmadığı kenarları çizgeden çıkarırsak ağaç oluşur. Bu ağaç tüm düğümleri içerir(eğer çizge bağlıysa).Çizge ayrık ise DFS tüm düğümlere ulaşamaz.

Zaman Karmaşıklığı

Çizgenin bağlı olduğunu varsayalım. DFS tüm düğümleri gezer ve tüm kenarları kontrol eder. DFS'nin zaman karmaşıklığı O(|V| + |E|) dir. Eğer çizge komşuluk matrisi kullanılarak gezilirse zaman karmaşıklığı O(|V|^2) olur.
V: Düğüm Kümesi
E: Kenar Kümesi

DFS ile çözebileceğiniz örnek sorular:

115A - Праздник

277A - Изучение языков

377A - Лабиринт

Полный текст и комментарии »

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

Автор ikbal, 12 лет назад, По-английски

_Eren_'e katkilarindan dolayi tesekkurler...

Breadth First Search ( BFS )


BFS'nin mantığı şöyledir. Bir düğümden başlayarak o düğümün tüm komşuları gezilir.

Daha sonra gezilen düğümlerin komşuları gezilir. Böylece çizge gezilir.

Algoritma

1. Kaynak düğümü kuyruğa( İlk giren ilk çıkar ) eklenir.
2. Kuyruğun başındaki düğümü çıkarılır.
3. Çıkarılan düğüm daha önce gezilmemiş ise , gezildi işareti konur ve gezilmemiş komşuları kuyruğa konur.
gezilmemiş komşuları kuyruğa konur.
4. Kuyruk boş değilse 2. adıma dönülür.





Çizge ayrık ise BFS tüm düğümlere ulaşamaz.

Zaman ve Hafıza Karmaşıklığı

En kötü durumda tüm düğüm ve kenarlar kontrol edilir.

Komşuluk listesi kullanılırsa zaman karmaşıklığı O(|V| + |E|) olur. Hafıza karmaşıklığı O(|V| + |E|) olur.

Komşuluk matrisi kullanılırsa zaman karmaşıklığı O(|V|2) olur. Hafıza karmaşıklığı O(|V|2) olur.

Not: |E| 1 ve |V|2 arasındadır.

V: Düğüm Kümesi

E: Kenar Kümesi

Полный текст и комментарии »

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

Автор ikbal, 12 лет назад, По-английски

Herkese merhaba!

Bugunden itibaren algoritma dersleri basliyor.

  • Algoritma derslerinin konulari sizin isteklerinize gore sekillenecek.

  • Anlatilmasi kararlastirilan konular aramizdaki daha tecrubeli gonulluler arasinda paylasilacak.

  • Yukarida bahsedilen gonulluler, sorumlulugu altina aldigi konuyu anlatan bir blog hazilayacak.

  • Blog iceriginde konu ile alakali gonullu tarafindan onerilen sorulara da yer verilecek.

  • Anlasilmayan noktalar blogun altinda comment atilarak sorulacak ve yine aramizdaki daha tecrubeliler bunlara ellerinden geldigince cevap verecek.

Grubun daha verimli olmasi adina sizlerden oneri almaktan memnuniyet duyarim.

Lutfen anlatilmasini istediginiz konu-algoritmayi bizlerle bu blogun altindan paylasin!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится