Sığ öncelikli arama

Bilgisayar biliminde, sığ öncelikli arama ya da enine arama, bir düğümlerini, başlangıç noktasına daha yakın olanlara öncelik vererek arayan bir algoritmadır. Algoritma ziyaret ettiği düğümlerin bütün komşularını bir 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ç ise kuyruk kullanmaya gerek olmaz.

Sığ öncelikli arama
Düğümlerin ziyaret etme sıraları
Sınıf	Arama algoritması
Zaman karmaşıklığı	${\displaystyle O(|V|+|E|)}$
Alan karmaşıklığı	${\displaystyle O(|V|)}$

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. 1959'da tarafından, bir labirentteki en kısa yolu bulmak için, 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.

Sözde kod

Canlandırmalı sığ öncelikli arama örneği.

Girdi olarak başlagıç düğümünü (ilk_düğüm) ve hedeflenen düğümü (son_düğüm) alan ve çıktı olarak bu ikisi arasındaki en kısa yolu bulmak için gerekli olan bilgiyi (yol_listesi) döndüren sözde kod aşağıdaki gibidir. Daha sonra yol_listesi kullanılarak, son_düğüm'den geriye doğru her düğümün öncülü takip edilerek tam yol bulunabilir.

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

Ayrıca bakınız

• Derin öncelikli arama
• Arama algoritması

Kaynakça

1. ^ ^{a b} Şeker, Şadi Evren. "Şekillerde Sığ Öncelikli Arama". bilgisayarkavramlari.sadievrenseker.com. Şadi Evren Şeker. 14 Haziran 2017 tarihinde kaynağından arşivlendi. Erişim tarihi: 19 Şubat 2018. 
2. ^ Morin, Pat; Tunç, Ayşegül (Ocak 2016). Açık Veri Yapıları (Java ile). İstanbul: ekitapprojesi.com. s. 416. Erişim tarihi: 18 Şubat 2018. 
3. ^ Zuse, Konrad (1972). Der Plankalkül (Tez) (Almanca). Konrad Zuse Internet Archive. ss. 96-105. 6 Mayıs 2018 tarihinde kaynağından arşivlendi. Erişim tarihi: 19 Şubat 2018. 
4. ^ (1959). Proceedings of the International Symposium on the Theory of Switching. Harvard University Press. ss. 285-292. 
5. ^ (2008). The Algorithm Design Manual. Springer. s. 480. doi:10.1007/978-1-84800-070-4_4. 
6. ^ ; Schardl, Tao B. (2010). A Work-Efficient Parallel Breadth-First Search Algorithm (or How to Cope with the Nondeterminism of Reducers) (PDF). ACM Symp. on Parallelism in Algorithms and Architectures. 15 Aralık 2017 tarihinde kaynağından arşivlendi (PDF). Erişim tarihi: 19 Şubat 2018. 
7. ^ Lee, C. Y. (1961). "An Algorithm for Path Connections and Its Applications". IRE Transactions on Electronic Computers.