Bu yazımızda veri yapısında BFS algoritmasını ele alacağız. Genişlik öncelikli arama, grafiği kök düğümden geçirmeye başlayan ve tüm komşu düğümleri araştıran bir grafik geçiş algoritmasıdır. Daha sonra en yakın düğümü seçer ve keşfedilmemiş tüm düğümleri araştırır. Geçiş için BFS kullanılırken grafikteki herhangi bir düğüm kök düğüm olarak düşünülebilir.
Grafiği geçmenin birçok yolu vardır ancak bunların arasında BFS en sık kullanılan yaklaşımdır. Bir ağacın veya grafik veri yapısının tüm köşelerini aramak için özyinelemeli bir algoritmadır. BFS, grafiğin her köşesini ziyaret edilen ve ziyaret edilmeyen olmak üzere iki kategoriye ayırır. Grafikteki tek bir düğümü seçer ve ardından seçilen düğüme bitişik tüm düğümleri ziyaret eder.
BFS algoritmasının uygulamaları
Genişlik öncelikli algoritmanın uygulamaları şu şekilde verilmiştir:
- BFS, belirli bir kaynak konumdan komşu konumları bulmak için kullanılabilir.
- Eşler arası bir ağda, BFS algoritması tüm komşu düğümleri bulmak için geçiş yöntemi olarak kullanılabilir. BitTorrent, uTorrent vb. gibi çoğu torrent istemcisi, ağdaki 'tohumları' ve 'eşleri' bulmak için bu işlemi kullanır.
- BFS, web tarayıcılarında web sayfası dizinleri oluşturmak için kullanılabilir. Web sayfalarını indekslemek için kullanılabilecek ana algoritmalardan biridir. Kaynak sayfadan geçmeye başlar ve sayfayla ilişkili bağlantıları takip eder. Burada her web sayfası grafikte bir düğüm olarak kabul edilir.
- BFS, en kısa yolu ve minimum yayılan ağacı belirlemek için kullanılır.
- BFS aynı zamanda Cheney'nin çöp toplama işlemini kopyalama tekniğinde de kullanılıyor.
- Bir akış ağındaki maksimum akışı hesaplamak için ford-Fulkerson yönteminde kullanılabilir.
Algoritma
Bir grafiği keşfetmek için BFS algoritmasında yer alan adımlar aşağıdaki gibidir:
Aşama 1: SET STATUS = 1 (hazır durum), G'deki her düğüm için
Adım 2: Başlangıç düğümü A'yı sıraya alın ve STATUS = 2'ye (bekleme durumu) ayarlayın
Aşama 3: QUEUE boşalıncaya kadar 4. ve 5. Adımları tekrarlayın
Adım 4: Bir düğüm N'yi sıradan çıkarın. İşleyin ve DURUM = 3'e (işlenmiş durum) ayarlayın.
Adım 5: N'nin hazır durumdaki (STATUS = 1) tüm komşularını kuyruğa alın ve ayarlayın
DURUMU = 2
(bekleme durumu)
[DÖNGÜ SONU]
Adım 6: ÇIKIŞ
BFS algoritması örneği
Şimdi bir örnek kullanarak BFS algoritmasının çalışmasını anlayalım. Aşağıdaki örnekte 7 köşesi olan yönlü bir grafik bulunmaktadır.
Yukarıdaki grafikte A Düğümünden başlayıp E Düğümünde bitecek BFS kullanılarak minimum 'P' yolu bulunabilir. Algoritma QUEUE1 ve QUEUE2 olmak üzere iki kuyruk kullanır. QUEUE1 işlenecek tüm düğümleri tutarken, QUEUE2 işlenen ve QUEUE1'den silinen tüm düğümleri tutar.
Şimdi A düğümünden başlayarak grafiği incelemeye başlayalım.
Aşama 1 - İlk olarak kuyruk1'e A'yı ve kuyruk2'ye NULL'u ekleyin.
QUEUE1 = {A} QUEUE2 = {NULL} Adım 2 - Şimdi A düğümünü kuyruk1'den silin ve kuyruk2'ye ekleyin. A düğümünün tüm komşularını kuyruk1'e ekleyin.
QUEUE1 = {B, D} QUEUE2 = {A} Aşama 3 - Şimdi, B düğümünü kuyruk1'den silin ve kuyruk2'ye ekleyin. B düğümünün tüm komşularını kuyruk1'e ekleyin.
QUEUE1 = {D, C, F} QUEUE2 = {A, B} 4. Adım - Şimdi D düğümünü kuyruk1'den silin ve kuyruk2'ye ekleyin. D düğümünün tüm komşularını kuyruk1'e ekleyin. D düğümünün tek komşusu F'dir çünkü zaten eklenmiş durumdadır, bu nedenle tekrar eklenmez.
QUEUE1 = {C, F} QUEUE2 = {A, B, D} Adım 5 - C düğümünü kuyruk1'den silin ve kuyruk2'ye ekleyin. C düğümünün tüm komşularını kuyruk1'e ekleyin.
QUEUE1 = {F, E, G} QUEUE2 = {A, B, D, C} Adım 5 - F düğümünü kuyruk1'den silin ve kuyruk2'ye ekleyin. F düğümünün tüm komşularını kuyruk1'e ekleyin. F düğümünün tüm komşuları zaten mevcut olduğundan onları tekrar eklemeyeceğiz.
QUEUE1 = {E, G} QUEUE2 = {A, B, D, C, F} Adım 6 - E düğümünü kuyruk1'den silin. Tüm komşuları zaten eklenmiş olduğundan onları tekrar eklemeyeceğiz. Artık tüm düğümler ziyaret edilir ve hedef düğüm E ile kuyruk2'de karşılaşılır.
QUEUE1 = {G} QUEUE2 = {A, B, D, C, F, E} BFS algoritmasının karmaşıklığı
BFS'nin zaman karmaşıklığı, grafiği temsil etmek için kullanılan veri yapısına bağlıdır. BFS algoritmasının zaman karmaşıklığı Ç(V+E) çünkü en kötü durumda BFS algoritması her düğümü ve kenarı araştırır. Bir grafikte köşe sayısı O(V), kenar sayısı ise O(E)'dir.
BFS'nin uzay karmaşıklığı şu şekilde ifade edilebilir: Ç(V) burada V köşe sayısıdır.
BFS algoritmasının uygulanması
Şimdi BFS algoritmasının Java'daki uygulamasını görelim.
Bu kodda grafiğimizi temsil etmek için bitişiklik listesini kullanıyoruz. Java'da Genişlik-Önce Arama algoritmasını uygulamak, bitişiklik listesiyle ilgilenmeyi çok daha kolay hale getirir, çünkü her düğüme bağlı düğümlerin listesinde yalnızca düğüm kuyruğun başından (veya başlangıcından) çıkarıldıktan sonra dolaşmamız gerekir.
Ağ ve Internet
Bu örnekte kodu göstermek için kullandığımız grafik şu şekilde verilmiştir:
import java.io.*; import java.util.*; public class BFSTraversal { private int vertex; /* total number number of vertices in the graph */ private LinkedList adj[]; /* adjacency list */ private Queue que; /* maintaining a queue */ BFSTraversal(int v) { vertex = v; adj = new LinkedList[vertex]; 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[vertex]; 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(10); graph.insertedge(0, 1); 2); 3); graph.insertedge(1, graph.insertedge(2, 4); graph.insertedge(3, 5); 6); graph.insertedge(4, 7); graph.insertedge(5, graph.insertedge(6, graph.insertedge(7, 8); system.out.println('breadth first traversal is:'); graph.bfs(2); pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/64/bfs-algorithm-3.webp" alt="Breadth First Search Algorithm"> <h3>Conclusion</h3> <p>In this article, we have discussed the Breadth-first search technique along with its example, complexity, and implementation in java programming language. Here, we have also seen the real-life applications of BFS that show it the important data structure algorithm.</p> <p>So, that's all about the article. Hope, it will be helpful and informative to you.</p> <hr></v;>