Basta fikrin sahibi t0nyukuk'a ve cevirilere katkisi olan herkese tesekkurler.
| Informatics Society for Turkish High Schools |
|---|
| Открытая |
| Зритель |
Вы пока не являетесь участником группы,
но можете запросить вступление в группу.
Basta fikrin sahibi t0nyukuk'a ve cevirilere katkisi olan herkese tesekkurler.
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:
_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
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!
| Название |
|---|


