Sığ öncelikli arama sayfasının kaynağını görüntüle

{{Algoritma bilgi kutusu
|sınıf=[[Arama algoritması]]
|resim=Breadth-first-tree.svg
|resim_açıklaması =Düğümlerin ziyaret etme sıraları
|veri1=[[Çizge]]
|zaman=<math>O(|V| + |E|)</math>
|alan=<math>O(|V|)</math>
}}
[[Bilgisayar bilimi]]nde, '''sığ öncelikli arama'''<ref name=seker>{{Web kaynağı | soyadı1 = Şeker | ad1 = Şadi Evren | başlık = Şekillerde Sığ Öncelikli Arama | url = http://bilgisayarkavramlari.sadievrenseker.com/2010/05/22/sekillerde-sig-oncelikli-arama/ | website = bilgisayarkavramlari.sadievrenseker.com | yayıncı = Şadi Evren Şeker | erişimtarihi = 19 Şubat 2018 | arşivurl = https://web.archive.org/web/20170614140746/http://bilgisayarkavramlari.sadievrenseker.com/2010/05/22/sekillerde-sig-oncelikli-arama/ | arşivtarihi = 14 Haziran 2017 | ölüurl =hayır}}</ref> ya da '''enine arama''',<ref name=morin>{{kitap kaynağı|soyadı1=Morin|ad1=Pat|soyadı2=Tunç|ad2=Ayşegül|başlık=Açık Veri Yapıları (Java ile)|tarih=Ocak 2016|yayıncı=ekitapprojesi.com|yer=İstanbul|sayfa=416|url=https://books.google.co.uk/books?id=sUKCCwAAQBAJ&pg=PA416&lpg=PA416&dq#v=onepage&q&f=false|erişimtarihi=18 Şubat 2018|dil=Türkçe}}</ref> bir [[Çizge (veri yapısı)|çizgenin]] [[Düğüm (bilgisayar bilimleri)|düğüm]]lerini, başlangıç noktasına daha yakın olanlara öncelik vererek [[Arama algoritması|arayan]] bir [[algoritma]]dır. Algoritma ziyaret ettiği düğümlerin bütün komşularını bir [[Kuyruk (veri yapısı)|kuyruğa]] ekler ve ziyaret edeceği düğümleri kuyruktaki sıraya göre seçer. Eğer arama yapılan çizge bir [[Ağaç (veri yapısı)|ağaç]] ise kuyruk kullanmaya gerek olmaz.<ref name=seker />

Sığ öncelikli arama 1945'te Michael Burke ve [[Konrad Zuse]] tarafından çizgelerde bağlı bileşenleri tespit etmek için geliştirilmiştir. Ancak, bu algoritmanın sunulduğu doktora tezi kabul edilmemiştir ve 1972 yılında yayınlanmıştır.<ref>{{Tez kaynağı |başlık=Der Plankalkül |yıl=1972 |yazarbağı=Konrad Zuse |url=http://zuse.zib.de/item/gHI1cNsUuQweHB6 |soyadı=Zuse |ad=Konrad |dil=Almanca |yayıncı=Konrad Zuse Internet Archive |sayfalar=96-105 |erişim-tarihi=19 Şubat 2018 |arşiv-url=https://web.archive.org/web/20180506141147/http://zuse.zib.de/item/gHI1cNsUuQweHB6 |arşiv-tarihi=6 Mayıs 2018 |ölüurl=hayır }}</ref>
1959'da [[Edward F. Moore|E. F. Moore]] tarafından, bir labirentteki en kısa yolu bulmak için,<ref>{{Konferans kaynağı|başlık=Proceedings of the International Symposium on the Theory of Switching |yazarbağı=Edward F. Moore |yıl=1959 |soyadı=Moore |ad=Edward F. |yayıncı=Harvard University Press |sayfalar=285-292}}</ref><ref name="skiena">{{Kitap kaynağı|sayfa=[https://archive.org/details/algorithmdesignm00skie_676/page/n489 480]  |başlık=The Algorithm Design Manual  |url=https://archive.org/details/algorithmdesignm00skie_676  |yıl=2008  |yazarbağı=Steven Skiena  |soyadı=Skiena  |ad=Steven  |yayıncı=Springer  |doi=10.1007/978-1-84800-070-4_4 }}</ref> 1961 yılında ondan bağımsız bir şekilde C. Y. Lee tarafından devrelerde bağlantıların belirlenmesi amacıyla tekrar icat edilmiştir.<ref>{{Konferans kaynağı  |başlık=A Work-Efficient Parallel Breadth-First Search Algorithm (or How to Cope with the Nondeterminism of Reducers)  |yıl=2010  |yazarbağı1=Charles E. Leiserson  |soyadı1=Leiserson  |ad1=Charles E. |ad2=Tao B. |konferans=ACM Symp. on Parallelism in Algorithms and Architectures  |soyadı2=Schardl  |url=http://supertech.csail.mit.edu/papers/pbfs.pdf  |erişim-tarihi=19 Şubat 2018  |arşivurl=https://web.archive.org/web/20171215094905/http://supertech.csail.mit.edu/papers/pbfs.pdf  |arşivtarihi=15 Aralık 2017  |ölüurl=hayır  }}</ref><ref>{{Dergi kaynağı|yıl=1961  |ad1=C. Y. |başlık=An Algorithm for Path Connections and Its Applications  |url=http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=5219222 |dergi=IRE Transactions on Electronic Computers  |soyadı1=Lee  }}</ref>

== Sözde kod ==
[[Dosya:Animated BFS.gif|küçükresim|upright=0.85|{{ortala|Canlandırmalı sığ öncelikli arama örneği.}}]]
''Girdi'' olarak başlagıç düğümünü (<code>ilk_düğüm</code>) ve hedeflenen düğümü (<code>son_düğüm</code>) alan ve ''çıktı'' olarak bu ikisi arasındaki en kısa yolu bulmak için gerekli olan bilgiyi (<code>yol_listesi</code>) döndüren sözde kod aşağıdaki gibidir. Daha sonra <code>yol_listesi</code> kullanılarak, <code>son_düğüm</code>'den geriye doğru her düğümün öncülü takip edilerek tam yol bulunabilir.

<syntaxhighlight>
fonksiyon sığ_öncelikli_arama (ilk_düğüm, son_düğüm):
  
  # listeleri yarat
  açık_liste := yeni kuyruk
  kapalı_liste := yeni kuyruk
  yol_listesi := yeni sözlük
  
  # aramayı başlat
  ilk_düğüm'ü açık_liste'ye ekle
  
  # ana döngü
  döngü (açık_liste boş değilse):
    
    # açılacak düğümü kuyruktan al
    açılan_düğüm := açık_liste'den çıkar
    
    # hedefi kontrol et
    eğer (açılan_düğüm = son_düğüm):
      
      döndür yol_listesi
      
    eğer_sonu
    
    komşu_listesi := açılan_düğüm'ün komşuları
    
    # komşu döngüsü
    döngü (komşu_listesi boş değilse):
    
      mevcut_komşu := komşu_listesi'nden çıkar
      
      eğer (mevcut_komşu kapalı_liste'de ve açık_liste'de yoksa):
        
        mevcut_komşu'yu açık_liste'ye ekle
        
        (mevcut_komşu: açılan_düğüm) ikilisini yol_listesi'ne ekle
              
      eğer_sonu
      
      açılan_düğüm'ü kapalı_liste'ye ekle
    
    döngü_sonu # komşu döngüsü
    
  döngü_sonu # ana döngü
  
  döndür boş liste
  
fonksiyon_sonu
</syntaxhighlight>

== Ayrıca bakınız ==
* [[Derin öncelikli arama]]
* [[Arama algoritması]]

==Kaynakça==
{{Kaynakça}}

[[Kategori:Arama algoritmaları]]
[[Kategori:Çizge algoritmaları]]