Derin öncelikli arama (depth first search)

Bir ağaç dolaşma algoritmasının (ağaç travers algoritma, ağaç kastetmek) ilk ÖNCE alt seviyesinde Bulunan komşularını araması durumudur.

Örneğin aşağıdaki ağacı ele alalım:

Ağacı dolaşma sırlaması örneğin 3, 2, 7, 1, 9, 8, 5 şeklindeyse bu dolaşmaya derin Öncelikli arama (derinlik ilk arama) ismi VERİLEBİLİR.

Bu arama sıralamasında, dolaşma Sıralaması aşağıdaki ihtimallerden birisi Olabilir:

LRN: Sol Sağ Düğüm (Sol Sağ Düğüm)

RLN: Sağ Sol Düğüm (Sağ Sol Düğüm)

RNL: Sağ Düğüm Sol (Sağ Düğüm Sol)

RLN: Sağ Sol Düğüm (Sağ Sol Düğüm)

Yani Öncelikle düğüm Sonra Altındaki Üyelere hareket edilir.

Sığ Öncelikli Arama (Genişlik İlk Arama)  algoritma Tipine Göre imkb:

NLR: Düğüm Sol Sağ (Düğüm Sol Sağ)

NRL: Düğüm Sağ Sol (Düğüm Sağ Sol)

ihtimallerinden birisi Tercih Edilebilir. Buradaki fark ilk bakılan düğümün, MEVCUT düğümün Altında Olan Bir düğüm Yerine Cardio seviyede olmasinin. Yani derin Öncelikli aramada, sığ aramadan Farklı Olarak ÖNCE düğümün alt seviyedeki düğümlerden Aramaya başlanır.

başladığımız il merkezinden gidilebilecek en uzak ile  gidilir.Daha  sonda gidecek Başka Yer kalmayınca Bir Önceki ile geri Dönerek oradan gidilebilecek en uzak ile gidilir ziyaretinde Daha Sonra Başlangıç ​​noktasına dönülür.Bu algoritmada hep Daha Derine gitme isteği ile hareket eder.Başka bır sekılde anlatilmak İSTENİRSE Bir ağacın ana köünden beligbli Bir ​​çıkmaza denk gelene Kadar ağacın derinliklerine doğru Işaretleyerek hareket edilir. Sonrasında çıkmaz il karşılaşınca geri dönülüp kardeş Olan düğüm aranır ziyaretinde kardeş Olan ilk düğüme rastlayınca tekrardan Daha derinlere doğru hareket edilir. İlk resimde DFS algoritmasının psuedo kodu bulunmaktadır.  

Aşağıdaki görselde imkb DFS algoritmasının örnek graf uzerinde Anlık çalışma Durumu gösterilmiştir.

Graf dolaşmak Click planlanan bu algoritmalar ile çok Farklı Bir Yol izleyeceğiz.Öncelikle internet Sitelerinin İçeriği de graf Yapısı oluşturmaktadır. Örneğin http://preciselyconcise.com/apis_and_installations/downloadables/jsoup/test.php  şu sitenin kaynak Kodunu inceleyecek olursak

Bu kodlar da Bir ağaç Yapısı olusturmus oluyorlar.

Bu ağaç yapısını oluşturduktan Sonra imkb Jsoup kullanarak bütün, sitelerde istedigimiz graf yapısını kurabilir.BFS DFS A.Ş. Algoritmaları ile aramak istedigimiz kelimelerin HTML kodlarına ulaşabiliriz. Bir site içerisinde Bulunan Tüm kelimelerde gezebilir, siralama arama yapabiliriz ettik.  

Şekillerde (Graph) sığ öncelikli arama (Breadth First Search, BFS)

Bu yazı,  ağaçlardaki sığ Öncelikli arama  ile karıştırılmamalıdır . Ağaçlar (ağaçları)  bilindiği Üzere yönlü dairesel olmayan şekillerdir (yönlendirilmiş Mercury grafik) dolayısıyla ağaçlar uzerinde bu yazıda anlatılan Sıra (kuyruk)  yapısına ve İhtiyaç Duyulmaz.

Sığ Öncelikli arama Bir Başlangıç ​​düğümünden başlayarak Sıradaki Komşuları dolaşan arama algoritmasıdır. Bu arama algoritmasında amaç ÖNCE Başlangıç ​​düğümüne Yakın Manzara düğümlere bakmaktır.

Bu arama şekli suya atılan Bir damlanın suda çıkardığı halkalara benzetilebilir. Başlangıç ​​düğümüne en Yakın Manzara halka Sonra ikinci Yakın Manzara halka Sonra diğerleri şeklinde giden bir arama algoritmasıdır ettik.

Bu Durumu aşağıdaki örnek Üzerinden anlamaya çalışalım:

Örnek Olarak yukarıda Bulunan şekli ele alalım. Örneğimizde Başlangıç ​​düğümü (düğüm) Olarak bir düğümünü seçtiğimizi ziyaretinde aranan düğümün e düğümü oldugunu düşünelim.  

A düğümünün komşuluk listesini (adjacency listesi) çıkarıyoruz:  

komşu (A) = {C, B}

Bu komşulara sırasıyla bakılıyor ziyaretinde bu komşuların komşuluk Listeleri çıkarılıyor:

bakılanlar: {A, B, C}

komşular = komşu (B), komşu (C) = {D, E, E}

Arana düğüm E, bu Adımda bulunmuştur.

Yukarıdaki örnekte görüldüğü Üzere Bir Sonraki derinliğe inilmeden sonra, o derinlikte Olan (Başlangıç ​​düğümüne O UZAKLIKTA Olan) Bütün Düğümler dolaşılıyor Ardından Bir alt seviyeye iniliyor ziyaretinde.

Yukarıdaki örnekte bütün, ağaç dolaşılmış gibi dusunulebilir. Örneğin sekil (grafik) aşağıdaki gibi olsaydı:

Bu DURUMDA Z düğümüne hiçbir, zaman bakılmayacaktı Çünkü aranan düğüm Z düğümünden Daha sığ Bir derinlikte Olacaktı.

Kısacası BFS arama algoritması ile aranan düğümün derinliğine Kadar Olan bütün, düğümlere bakılır ancak bu derinlikten Daha aşağıda Olan düğümlere bakılmasına gerek yoktur.

Sığ Öncelikli Arama (Breadth First Search , BFS)

Bir ağaç dolaşma algoritmasının (ağaç hareket algoritması, ağaç geçişi) ilk ÖNCE Cardio seviyede Bulunan komşularını araması durumudur.

Örneğin aşağıdaki ağacı ele alalım:

Ağacı dolaşma sırlaması örneğin 5,7,8,3,2,1,9 şeklindeyse bu dolaşmaya sığ Öncelikli arama ismi VERİLEBİLİR.

Bu arama sıralamasında, dolaşma Sıralaması aşağıdaki ihtimallerden birisi Olabilir:

NLR: Düğüm Sol Sağ (Düğüm Sol Sağ)

NRL: Düğüm Sağ Sol (Düğüm Sağ Sol)

Yani Öncelikle düğüm Sonra Altındaki Üyelere hareket edilir.

Derin Öncelikli Arama (derinlik Önce Arama)  algoritma Tipine Göre imkb:

LRN: Sol Sağ Düğüm (Sol Sağ Düğüm)

RLN: Sağ Sol Düğüm (Sağ Sol Düğüm)

RNL: Sağ Düğüm Sol (Sağ Düğüm Sol)

LNR: Sol Düğüm Sağ (Sol Düğüm Sağ)

ihtimallerinden birisi Tercih Edilebilir. Buradaki fark ilk bakılan düğümün, MEVCUT düğümün Altında Olan Bir düğüm olmasinin. Yani sığ Öncelikli aramada Olduğu gibi Cardio seviyedeki düğümlerden ÖNCE alt seviyedeki düğümlere bakılır.

BFS (ilk arama genişlik) algoritmasının çalışma mantığı şu şekildedir. Bir düğüm dan başlayarak Ilgili düğüm un Tüm Komşuları gezilir Verilen. Daha Sonra gezilen komşuların Komşuları gezilerek Verilen grafiktir gezilmiş olur.

Algoritma

1. Fonksiyona Gönderilen düğümü kuyruğa atılır.
2. Kuyruk boşalıncaya Kadar döngü sürdürülür.
3. Sıradaki düğümü kuyruktan çıkarılır.
4. Çıkarılan düğüm Daha Önce gezilmemiş imkb, gezildi işareti Konur gezilmemiş Komşuları kuyruğa Konur A.Ş..

Sözde Kodunu şöyle yazabiliriz.

^? View Code  C

Kamu void bfs ( ) { // BFS Kuyruk veri yapısı kullanır Kuyruk q = new n = ( Düğüm ) q. çıkartın ( ) ; Düğüm düğümler arasında ziyaret mülkiyet clearNodes ( ) ; }

Alttaki sekil de bir grafik Verilen ın gezilirken nasıl renklendirildiğini görebilirsiniz

AYRICA göster buradaki animasyonu Izleyebilirsiniz.  

Şekil 1

Şekil 1 Örneğin Click bfs algoritmasıda c Kodunu yazmak Hakkında istersek şu sekılde Bir kod yazabiliriz.

^? View Code  C

#include <stdio.h> #include <math.h> #include <stdlib.h> #include <time.h>   Yapısı Başlangıcı ///////////////////// typedef struct köşe Öğe ; struct düğüm { Öğe olsun ( ) { eğer ( ! isEmpty ( ) ) { Item Kuyruk) "boş; }   } void koymak ( Öğe Yapısı Sonu - & Gt; color = , ver , koyun ( arr [ FindIndex ( arr , mem - & gt ; harf ) ] ) ; printf ( "% C kuyruğu koyar \ n " , arr [ FindIndex ( arr , mem - & gt ; harf ) ] . madde ) ; } mem = mem - & gt ; yanındaki , } ver. renk = 'B' ; printf ( "% C - & gt; color = Siyah \ n " , . ver madde ) ; } } int ana ( ) { queueInıt ( 1 ) ; // Kuyruk çıkacağı başlatılamıyor   struct Vertex * arr = ( struct köşe * ) malloc ( sizeof ( struct köşe ) * 6 ) ;   arr [ 0 ] . item = 'A' ; arr [ 1 ] . item = 'B' ; arr [ 2 ] . item = 'C' ; arr [ 3 ] . item = 'D' ; arr [ 4 ] . item = 'E' ; arr [ 5 ] . item = 'F' ; //Bağlantılar atanıyor arr [ 0 ] . connection = ( struct members * ) malloc ( sizeof ( struct members ) ) ; arr [ 0 ] . connection -& gt ; letter = 'D' ; arr [ 0 ] . connection -& gt ; next = NULL ;   arr [ 1 ] . connection = ( struct members * ) malloc ( sizeof ( struct members ) ) ; arr [ 1 ] . connection -& gt ; letter = 'C' ; arr [ 1 ] . connection -& gt ; next = ( struct members * ) malloc ( sizeof ( struct members ) ) ; arr [ 1 ] . connection -& gt ; next -& gt ; letter = 'E' ; arr [ 1 ] . connection -& gt ; next -& gt ; next = NULL ;   arr [ 2 ] . Bağlantı = null ;   arr [ 3 ] . connection = ( struct members * ) malloc ( sizeof ( struct members ) ) ; arr [ 3 ] . connection -& gt ; letter = 'B' ; arr [ 3 ] . connection -& gt ; next = ( struct members * ) malloc ( sizeof ( struct members ) ) ; arr [ 3 ] . connection -& gt ; next -& gt ; letter = 'F' ; arr [ 3 ] . connection -& gt ; next -& gt ; next = NULL ;   arr [ 4 ] . connection = ( struct members * ) malloc ( sizeof ( struct members ) ) ; arr [ 4 ] . connection -& gt ; letter = 'D' ; arr [ 4 ] . connection -& gt ; next = ( struct members * ) malloc ( sizeof ( struct members ) ) ; arr [ 4 ] . connection -& gt ; next -& gt ; letter = 'C' ; arr [ 4 ] . connection -& gt ; next -& gt ; next = ( struct members * ) malloc ( sizeof ( struct members ) ) ; arr [ 4 ] . connection -& gt ; next -& gt ; next -& gt ; letter = 'F' ; arr [ 4 ] . connection -& gt ; next -& gt ; next -& gt ; next = NULL ;   arr [ 5 ] . Bağlantı = null ;   bfs ( arr , 0 ) ; iade 0 ; }

gelmez diyenlere inat ???? hoşgeldin uçan Hollandalı Robin van Persie

Yunanistan`da nakit sıkıntısı nedeniyle Türk lirası ve Bulgar levası kullanılmaya başlandı.