Enlemesine Arama (BFS)

Graflar O(V + E) O(V)

Bir kuyruk kullanarak grafı seviye seviye keşfeder — ağırlıksız graflarda en kısa yolların temelidir.

Başlangıç düğümü

1/47

Kaynak 0 ziyaret edildi olarak işaretleniyor.

DeğişmezKuyruk en fazla iki komşu katmandan düğüm tutar, bu yüzden düğümler kaynağa uzaklığı azalmayacak sırada çıkar.

mevcutsınırziyaret edildiağaç kenarı

bfs.c

#define V 6
 
void bfs(int graph[V][V], int start) {
    int visited[V] = {0};
    int queue[V], front = 0, rear = 0;
 
    visited[start] = 1;
    queue[rear++] = start;
 
    while (front < rear) {
        int u = queue[front++];
        printf("%d ", u);
        for (int v = 0; v < V; v++) {
            if (graph[u][v] && !visited[v]) {
                visited[v] = 1;
                queue[rear++] = v;
            }
        }
    }
}

Enlemesine Arama (BFS) nasıl çalışır?

Halkalar hâlinde dışa doğru keşfet: önce 1 uzaklıktaki tüm düğümler, sonra 2, … — FIFO kuyrukla. Bir düğüme ilk ulaşma her zaman en az kenarlı yoldan olur.

Ne zaman kullanılır?

Ağırlıksız graflarda en kısa yol, seviye seviye işleme, bağlantılılık kontrolleri.