Ziyaret edilen
Kuyrukta
İncelenen kenar

  • Şu anki
  • Kuyrukta
  • Ziyaret edilen
  • Yol
Tıklamayla belirlenen

Genişlik öncelikli arama hakkında daha fazla

Genişlik öncelikli arama (BFS)

Genişlik öncelikli arama bir grafı halkalar hâlinde keşfeder: önce başlangıcın yanındaki her düğüm, sonra iki kenar uzaktaki her düğüm ve böyle devam eder. Bunu bir kuyrukla yapar: ilk giren ilk çıkar. Başlamak için bir düğüme tıklayın, isterseniz bir hedef seçin ve aramayı adım adım ilerletin: kuyruğun büyüyüp küçüldüğünü, her düğümün uzaklığını aldığını ve bir en kısa yolun belirdiğini görün. Aramayı izlemek için Oynat'a basın ya da adım adım ilerlemek için Adım ve Geri'yi kullanın. Herhangi bir yere atlamak için adım kaydırıcısını sürükleyin. Bir düğümü başlangıç yapmak için ona tıklayın; tıklamayı Hedef'e çevirip başka bir düğüme tıklayarak oraya giden en kısa yolu arayın. Her düğümdeki sayı, başlangıca olan uzaklığıdır; grafın altındaki satır ise kuyruktur. Yeni graf başka bir graf oluşturur; kaç düğüm ve kenar olacağını seçin. Pano seçiliyken ok tuşları adım atar, boşluk tuşu oynatır ve duraklatır, Home ve End başa ve sona atlar.

Nasıl çalışır

  1. Bir düğümü başlangıç yapmak için ona tıklayın. Yol aramak için tıklamayı Hedef'e çevirin ve başka bir düğüme tıklayın.
  2. Oynat'a basın ya da adım adım ilerlemek için Adım ve Geri'yi kullanın. Aramada herhangi bir yere atlamak için adım kaydırıcısını sürükleyin.
  3. Grafın altındaki kuyruğu ve her düğümdeki uzaklığı izleyin. Yeni graf, denemeniz için başka bir graf oluşturur.

Genişlik öncelikli arama nasıl çalışır

Başlangıç düğümünü uzaklık 0 ile bir kuyruğa koyun. Sonra şunu tekrarlayın: kuyruğun önündeki düğümü alın ve komşularının her birine bakın. Henüz görülmemiş bir komşu, aldığınız düğümden bir fazla uzaklık alır, o düğümü kendisine ulaşılan yol olarak hatırlar ve kuyruğun sonuna eklenir. Daha önce görülen komşular atlanır. Kuyruk boşaldığında ulaşılabilen her düğümün uzaklığı bellidir.

En kısa yolları neden bulur

Kuyruk düğümleri bulundukları sırayla verir ve düğümler halka halka bulunur: uzaklığı 1 olan tüm düğümler, uzaklığı 2 olan herhangi bir düğümden önce kuyruğa girer ve böyle devam eder. Yani bir düğüme ilk kez ulaşıldığında, mümkün olan en az kenarlı bir yolla ulaşılmıştır. Hatırlanan düğümleri hedeften başlangıca doğru geri izlemek o yolu verir. Bu yalnızca kenarları sayar; kenarların uzunlukları farklıysa Dijkstra algoritması gerekir.

Sık sorulan sorular

Genişlik öncelikli arama nedir?

Bir grafı bir başlangıç düğümünden keşfetmenin bir yolu: önce tüm komşularını, sonra onların komşularını ziyaret ederek halka halka ilerler. Düğümleri bulundukları sırada tutmak için bir kuyruk kullanır.

Genişlik öncelikli arama en kısa yolu bulur mu?

Evet, her kenar eşit sayıldığında: BFS bir düğüme ilk ulaştığında mümkün olan en az kenarı kullanmıştır. Uzunlukları farklı kenarlar için bunun yerine Dijkstra algoritmasını kullanın.

BFS ile DFS arasındaki fark nedir?

Genişlik öncelikli arama bir kuyruk kullanır ve halka halka eşit şekilde yayılır. Derinlik öncelikli arama bir yığın (ya da özyineleme) kullanır ve geri dönmeden önce bir yolu gidebildiği kadar derine izler. BFS kenar sayısına göre en kısa yolları bulur; DFS bulmaz, ama döngüleri bulmak ve topolojik sıralama için kullanışlıdır.

Genişlik öncelikli arama ne kadar hızlıdır?

Her düğümü kuyruktan bir kez çıkarır ve her kenara iki ucundan bakar, bu yüzden iş düğüm sayısı ile kenar sayısının toplamıyla birlikte artar.

Grafım bir yere gönderiliyor mu?

Hayır. Graf tarayıcınızda oluşturulur ve aranır, son ayarlarınız da bu tarayıcının yerel depolamasında kalır.

Denemeye hazır mısınız?

PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.

Editöre Git