Genişlik İlk Arama Algoritması: Genel Bakış, Önem ve Uygulamalar

Grafikler etrafımızda. Bir grafik, birbirine bağlı düğümler ve kenarlar ağı olarak düşünülebilir. Facebook'taki arkadaşlarınız, LinkedIn'deki bağlantılarınız veya Twitter/Instagram takipçileriniz sosyal grafiğinizi oluşturur. Benzer şekilde, A noktasından B noktasına gitmek istiyorsanız, bunu Google Haritalar'da görselleştirilebilen birden fazla rota üzerinden yapabilirsiniz.

A noktasından B noktasına tüm bu çoklu rota seçenekleri de bir grafik oluşturmaktadır. Grafikler, hem akademide hem de gerçek dünyada karşılaştığımız en yaygın veri yapıları arasındadır, çünkü her yerde bulunurlar. Ve bir grafik üzerinde gerçekleştirilebilecek en sık işlemlerden biri de grafik geçişidir.

Grafik Geçişi nedir?

Grafik Geçişi, bir grafikteki her düğümü tam olarak bir kez hız ve hassasiyetle ziyaret etme yöntemidir. Sonsuz bir döngüye takılmadan ziyaret edilen düğümlerin sırasını yazdırmanızı sağlayan gelişmiş bir grafik arama algoritmasıdır. Derinlik-İlk Arama , Genişlik-İlk Arama , Djikstra'nın Algoritması , A-Star Algoritması ve daha fazlası gibi birçok grafik geçiş algoritması vardır .

Bu makale, Genişlik İlk Arama Algoritmasına veya BFS'ye derinlemesine bir dalış yapacak .

Grafik Yapısı

BFS başlığının altına ayrıntılı bir göz atmadan önce, yukarıdaki grafiğin yardımıyla bazı grafik terminolojilerine aşina olalım:

Kök Düğüm – Geçiş sürecini başlattığınız düğüm. Basitlik için, A'yı kök düğüm olarak kabul edebiliriz.

Düzeyler – Düzey, kök düğümden eşit uzaklıkta olan tüm düğümlerin bir koleksiyonudur. Dolayısıyla, A düğümünün Düzey 0'da olduğunu düşünürsek, B ve C düğümleri Düzey 1'deyken D, E ve F düğümleri düzey 2'dedir. Bir düğümün düzey numarasını belirlemek için basit bir buluşsal yöntem, sayıyı saymaktır. söz konusu düğüm ve kök düğüm arasındaki kenarların sayısı. Bunun yalnızca kök düğümü Düzey 0'da tanımladığınızda işe yarayacağını unutmayın.

Ana Düğüm – Bir düğümün ana düğümü, kendisinden bir seviye yukarıda ve ona bitişik olan düğümdür. Söz konusu düğümün kaynaklandığı düğüm olarak düşünülebilir. A, B ve C'nin ebeveyn düğümüdür.

Alt / Çocuk Düğümleri – Dallanan ve bir üst düğüme bitişik olan düğüm(ler). B ve C, A'nın alt düğümleridir

Okuyun: En İyi 10 Veri Görselleştirme Tekniği

BFS, bir ağacı veya grafiği verimli bir şekilde keşfetmek için bir grafik geçiş algoritmasıdır. Algoritma, bir ilk düğümle (kök düğüm) başlar ve daha sonra, belirli bir daldan o daldaki tüm düğümlere kadar inen derinlik öncelikli yerine, genişlik-birinci tarzda, ona bitişik tüm düğümleri keşfetmeye devam eder. ziyaret edilmektedir. Basitçe söylemek gerekirse, o seviyedeki tüm düğümler ziyaret edilene ve işaretlenene kadar bir seviye aşağı hareket etmeden grafiği seviye bazında geçer.

İlk giren ilk çıkar (FIFO) ilkesine göre çalışır ve bir kuyruk veri yapısı kullanılarak uygulanır. Bir düğüm ziyaret edildiğinde, bir kuyruğa eklenir. Daha sonra kaydedilir ve tüm alt düğümleri kuyruğa eklenir. Bu işlem, grafikteki tüm düğümler ziyaret edilip kaydedilinceye kadar devam eder.

Yukarıda verilen grafik için BFS algoritması için ayrıntılı kuyruk işlemlerine bakalım:

() – kuyruğu belirtir

[] – yazdırılan çıktıyı belirtir

1. A'yı kuyruğa ekleyin (a)
2. A yazdırın, B ve C'yi kuyruğa ekleyin (cb)[a]
3. B'yi yazdırın, alt düğümleri D ve E'yi kuyruğa ekleyin (edc)[ba]
4. C yazdırın, alt düğümü F'yi kuyruğa ekleyin (beslenir)[cba]
5. D yazdırın, alt düğümünü kuyruğa ekleyin. Hiç yok. (fe)[dcba]
6. Alt düğümü F zaten kuyruğa eklenmiş olan E'yi yazdırın. (f)[edcba]
7. F yazdırın. [fedcba]

BFS Algoritmasını Önemli Kılan Nedir?

Geniş veri kümelerini hızlı bir şekilde aramak için bir yöntem olarak BFS'yi dağıtmanın sayısız nedeni vardır. Onu geliştiriciler ve veri mühendisleri için tercih edilen seçenek yapan göze çarpan özelliklerden bazıları şunlardır:

• BFS, grafikteki tüm düğümleri etkili bir şekilde keşfedebilir ve hepsini keşfetmek için mümkün olan en kısa yolu bulabilir.
• Tüm grafiği geçmek için gereken yineleme sayısı, diğer arama algoritmalarından daha azdır.
• Kuyruk kullanılarak uygulandığı için mimarisi sağlam, güvenilir ve zariftir.
• Diğer algoritmalarla karşılaştırıldığında, BFS'nin çıktısı kesin ve hatasızdır.
• BFS yinelemeleri, sonsuz bir döngüye yakalanma riski olmadan sorunsuz bir şekilde ilerler.

Ödeme: Çoğaltabileceğiniz Veri Görselleştirme Projeleri

BFS Algoritmasının Uygulamaları

Basitliği ve kurulum kolaylığı nedeniyle, BFS algoritması, çeşitli önemli gerçek dünya durumlarında yaygın bir kullanım bulmuştur. Öne çıkan birkaç uygulamaya bakalım:

Arama Motoru Tarayıcıları – Google veya Bing'in olmadığı bir dünya hayal etmeyi deneyin. Yapamazsın. Arama motorları internetin bel kemiğidir. Ve BFS algoritması, arama motorlarının bel kemiğidir. Web sayfalarını indekslemek için kullanılan birincil algoritmadır. Algoritma, yolculuğuna kaynak sayfadan (kök düğüm) başlar ve ardından o kaynak sayfadaki tüm bağlantıları geniş bir şekilde takip eder. Her web sayfası, grafikte bağımsız bir düğüm olarak düşünülebilir.

Ağırlıksız Grafik Geçişleri – BFS, ağırlıksız bir grafikte en kısa yolu ve minimum yayılan ağacı belirleyebilir. En kısa rotayı bulmak, yalnızca BFS'nin ideal olarak uygun olduğu en az sayıda kenara sahip bir yol bulmakla ilgilidir. En az sayıda düğümü ziyaret ederek işi halledebilir.

GPS Navigasyonu – BFS, başlangıç ​​noktanızdan tüm olası komşu konumları yüzeye çıkarmak için GPS sistemlerinden yararlanır ve A noktasından B noktasına sorunsuz bir şekilde gitmenize yardımcı olur.

Yayın - Yayın ağı, sinyalleri ve verileri taşımak için paketleri birimler olarak kullanır. BFS algoritması, bu paketleri, ulaşmaları gereken ağdaki tüm düğümlere gidecek şekilde yönlendirir.

P2P Ağları – Torrentler veya diğer dosya paylaşım ağları, P2P iletişimine dayanır. BFS, veri aktarımının daha hızlı gerçekleşebilmesi için en yakın düğümleri bulmak için mükemmel çalışır.

Ayrıca Okuyun: Veri Görselleştirmenin Faydaları

Çözüm

Ergo, Genişlik İlk Arama Algoritması , modern internetin en önemli algoritmalarından biridir. Umarım bu blog, arama algoritması keşiflerinizde kullanışlı bir başlangıç ​​noktası görevi görür.

UpGrad'da barındırılan IIIT Bangalore tarafından sunulan PG Diploma in Data Science'ı seçmenizi öneririz çünkü burada kurs eğitmenleriyle 1-1 sorgularınızı alabilirsiniz. Sadece teorik öğrenmeye odaklanmakla kalmaz, aynı zamanda öğrencileri gerçek dünya projeleriyle yüzleşmeye hazırlamak için gerekli olan ve size Veri Biliminde yüksek ücretli işler almanıza yardımcı olan Hindistan'ın 1. NASSCOM sertifikasını sağlayan pratik temelli bilgiye önem verir.