![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/3/33/Breadth-first-tree.svg/langtr-640px-Breadth-first-tree.svg.png&w=640&q=50)
Sığ öncelikli arama
From Wikipedia, the free encyclopedia
Bilgisayar biliminde, sığ öncelikli arama[1] ya da enine arama,[2] 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.[1]
Sığ öncelikli arama | |
---|---|
![]() Düğümlerin ziyaret etme sıraları | |
Sınıf | Arama algoritması |
Zaman karmaşıklığı | |
Alan karmaşıklığı |
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.[3] 1959'da E. F. Moore tarafından, bir labirentteki en kısa yolu bulmak için,[4][5] 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.[6][7]