Sığ öncelikli arama

Bilgisayar biliminde, sığ öncelikli arama ya da enine arama, bir çizgenin 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 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 E. F. Moore 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 

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

Arama algoritmaları
Çizge algoritmaları