BFS nedir?
Genişlik-Önce Arama (BFS), her düğümün komşularını kök düğümden başlayarak geçiş kuyruğuna ekleyerek geçiş düğümlerini temel alır. Bir grafiğin BFS'si, grafiklerin döngülere sahip olabilmesi dışında, bir ağacınkine benzer. Derinlik öncelikli aramanın aksine, belirli bir derinlikteki tüm komşu düğümler bir sonraki seviyeye geçmeden önce araştırılır.
BFS Algoritması
Bir grafiği keşfetmek için genişlik öncelikli aramayı kullanmanın adımları şunlardır:
- Grafiğin bitişiklik matrisi veya bitişiklik listesi için verileri alın.
- Bir kuyruk oluşturun ve onu öğelerle doldurun.
- Kök düğümü etkinleştirin (bu, kök düğümün kuyruğun başında olması anlamına gelir).
- Kuyruğun başını (veya başlangıç öğesini) sıradan çıkarın, ardından soldan sağa kuyruğun yakınındaki tüm düğümleri sıraya alın. Bir düğümün yakınlarda araştırılması gereken düğümleri yoksa basitçe kafayı çıkarın ve işlemi sürdürün. (Not: Daha önce araştırılmış veya kuyrukta olan bir komşu ortaya çıkarsa, onu kuyruğa almayın; bunun yerine atlayın.)
- Sıra boşalana kadar bu şekilde devam edin.
BFS Uygulamaları
Algoritmanın esnekliği nedeniyle Genişlik Öncelikli Arama gerçek dünyada oldukça kullanışlıdır. Bunlar bunlardan bazıları:
Java dize biçimi uzun
- Eşler arası ağda eş düğümler keşfedilir. BitTorrent, uTorrent ve qBittorent gibi çoğu torrent istemcisi, ağdaki 'tohumları' ve 'eşleri' bulmak için bu işlemi kullanır.
- Dizin, web taramasında grafik geçiş teknikleri kullanılarak oluşturulmuştur. Prosedür, kaynak sayfanın kök düğüm olmasıyla başlar ve kaynak sayfaya bağlı tüm ikincil sayfalara doğru ilerler (ve bu süreç devam eder). Özyineleme ağacının azaltılmış derinliği nedeniyle, Genişlik Öncelikli Aramanın burada doğal bir avantajı vardır.
- GPS kullanan GPS navigasyon sistemlerinin kullanımı, yakındaki siteleri bulmak için geniş kapsamlı bir arama gerçekleştirir.
- Çöp toplamak için genişlik öncelikli arama kavramını kullanan Cheney'nin tekniği kullanılıyor.
Örnek BFS Geçişi
Başlamak için basit bir örneğe bakalım. Kök düğüm olarak 0 ile başlayacağız ve grafikte aşağı doğru ilerleyeceğiz.
Aşama 1: Kuyruğa al(0)
Sıra
| 0 |
Adım 2: Kuyruktan Çıkarma(0), Kuyruktan Çıkarma(1), Kuyruktan Çıkarma(3), Kuyruktan Çıkarma(4)
Sıra
| 1 | 3 | 4 |
Aşama 3: Sıradan Çıkarma(1), Sıradan Çıkarma(2)
Sıra
| 3 | 4 | 2 |
Adım 4: Kuyruktan Çıkar(3), Kuyruktan Çıkar(5). 0 zaten araştırıldığı için sıraya 1'i tekrar eklemeyeceğiz.
Sıra
| 4 | 2 | 5 |
Adım 5: Kuyruktan çıkarma(4)
Sıra
| 2 | 5 |
Adım 6: Kuyruktan çıkarma(2)
Sıra
mylivecricket.in
| 5 |
Adım 7: Kuyruktan çıkarma(5)
Sıra
Sıra artık boş olduğundan işlemi durduracağız.
Genişlik-Önce Arama Java Programı
Kodla ilgilenmenin birkaç yaklaşımı vardır. Çoğunlukla Java'da geniş kapsamlı aramanın uygulanmasına ilişkin adımları tartışacağız. Grafikleri depolamak için bir bitişiklik listesi veya bir bitişiklik matrisi kullanılabilir; her iki yöntem de kabul edilebilir. Komşuluk listesi kodumuzdaki grafiğimizi temsil etmek için kullanılacaktır. Java'da Genişlik-Önce Arama algoritmasını uygularken, bitişiklik listesiyle uğraşmak çok daha kolaydır çünkü her düğüme bağlı düğümlerin listesinde yalnızca düğüm, düğümün başından (veya başlangıcından) kuyruktan çıkarıldıktan sonra dolaşmamız gerekir. sıra.
Kodu göstermek için kullanılan grafik, önceki örnekte kullanılan grafikle aynı olacaktır.
BFSTraversal.java
import java.io.*; import java.util.*; public class BFSTraversal { private int node; /* total number number of nodes in the graph */ private LinkedList adj[]; /* adjacency list */ private Queue que; /* maintaining a queue */ BFSTraversal(int v) { node = v; adj = new LinkedList[node]; for (int i=0; i<v; i++) { adj[i]="new" linkedlist(); } que="new" void insertedge(int v,int w) adj[v].add(w); * adding an edge to the adjacency list (edges are bidirectional in this example) bfs(int n) boolean nodes[]="new" boolean[node]; initialize array for holding data int a="0;" nodes[n]="true;" que.add(n); root node is added top of queue while (que.size() !="0)" n="que.poll();" remove element system.out.print(n+' '); print (int i="0;" < adj[n].size(); iterate through linked and push all neighbors into if (!nodes[a]) only insert nodes they have not been explored already nodes[a]="true;" que.add(a); public static main(string args[]) bfstraversal graph="new" bfstraversal(6); graph.insertedge(0, 1); 3); 4); graph.insertedge(4, 5); graph.insertedge(3, graph.insertedge(1, 2); 0); graph.insertedge(2, graph.insertedge(5, system.out.println('breadth first traversal is:'); graph.bfs(0); pre> <p> <strong>Output:</strong> </p> <pre> Breadth First Traversal for the graph is: 0 1 3 4 2 5 </pre> <hr></v;>