BFS, kök düğümden başlayarak tüm elemanları tarayan ve komşulukları ortaya çıkaran bir graf arama algoritmasıdır.

Çalışması sırasında son düğüme oluşana dek, keşfedilmiş tüm düğümlere komşu henüz keşfedilmemiş düğümleri keşfetme mantığını yürütür. Diklemesine değil, yataylamasına büyümeyi hedefler.

Düğümlerin keşfediliş sıralarına göre farklı ağaçlar oluşturulabilir.

bfs

 

Pseudocode:

unmark all vertices
choose some starting vertex x
mark x
list L = x
tree T = x

while L nonempty
choose some vertex v from front of list
visit v
for each unmarked neighbor w
    mark w
    add it to end of list
    add edge (v,w) to T

Liste olarak kuyruk tutmalıyız. FIFO kuralı uygulanacak.

 

Kuyruk kullanmadan da yapılabilir. Aşağıda yer alan C++ kodunda kuyruk kullanılmamıştır.

bool Discovered[num];
for (int k = 0; k < num; k++)
    Discovered[k] = false;

Node BFStree[num];

int i = 0;
BFStree[i].data = 0;
Node *temp;

Discovered[i] = true;

while ( i < num ) {
    temp = &BFStree[i];
    for( int k = 0 ; k < num ; k++ ) {
        if ( matris[i][k] == 1 && !Discovered[k] ) {
            Discovered[k] = true;
            Node *newNode = new Node(k);
            temp->next = newNode;
            temp = newNode;
        }
    }

    i++;
    BFStree[i].data = i;
}

Not: Yukarıdaki kodu çalıştırmak için Adjacency matris kullanılmıştır. “num” adındaki değişken ise grafta yer alan eleman sayısını göstermektedir.

 

Sonuç olarak Adjencency matrisi sol aşağıdaki gibi olan bir grafın bfs algoritması sonucu oluşan spanning ağacı sağ aşağıdaki gibidir.

0 1 1 0 0 0 0 0                               1 2 3
1 0 1 1 1 0 0 0     2 4 5
1 1 0 0 1 0 1 1     3 7 8
0 1 0 0 1 0 0 0                   4    
0 1 1 1 0 1 0 0     5 6  
0 0 0 0 1 0 0 0     6    
0 0 1 0 0 0 0 1     7    
0 0 1 0 0 0 1 0     8    
Tags: , , , , | Categories: Algoritma | C++