Genişlik Öncelikli Arama Breadth-First Search (BFS)

typedef struct {
    int* veri;
    int  bas, son, kapasite;
} Kuyruk;

Kuyruk* kuyrukOlustur(int kap) {
    Kuyruk* q = malloc(sizeof(Kuyruk));
    q->veri = malloc(kap * sizeof(int));
    q->bas = q->son = 0;
    q->kapasite = kap;
    return q;
}
void  enqueue(Kuyruk* q, int v)  { q->veri[q->son++] = v; }
int   dequeue(Kuyruk* q)          { return q->veri[q->bas++]; }
bool  kuyrukBos(Kuyruk* q)       { return q->bas == q->son; }

/*
 * BFS — Genişlik Öncelikli Arama
 * graf: komşuluk listesi (önceki bölümdeki ListeGraf)
 * baslangic: kaynak düğüm
 * mesafe[]: her düğümün kaynaktan mesafesi (-1 = ulaşılamaz)
 * ebeveyn[]: BFS ağacında ebeveyn (-1 = kök veya ulaşılamaz)
 */
void bfs(ListeGraf* graf, int baslangic,
         int mesafe[], int ebeveyn[]) {

    int V = graf->dugumSayisi;

    // 1) Başlangıç durumu: tümü keşfedilmemiş
    bool* ziyaret = calloc(V, sizeof(bool));
    for (int i = 0; i < V; i++) {
        mesafe[i]  = -1;
        ebeveyn[i] = -1;
    }

    // 2) Kaynak düğümü başlat
    Kuyruk* q = kuyrukOlustur(V);
    ziyaret[baslangic] = true;
    mesafe[baslangic]  = 0;
    enqueue(q, baslangic);

    // 3) Ana döngü
    while (!kuyrukBos(q)) {
        int u = dequeue(q);

        // u'nun tüm komşularını tara
        KomsulukNode* komsu = graf->listeler[u];
        while (komsu) {
            int v = komsu->hedef;

            if (!ziyaret[v]) {         // beyaz → gri
                ziyaret[v]  = true;
                mesafe[v]   = mesafe[u] + 1;
                ebeveyn[v]  = u;
                enqueue(q, v);
            }
            komsu = komsu->next;
        }
        // u artık siyah (tüm komşuları işlendi)
    }

    free(ziyaret);
    free(q->veri);
    free(q);
}

void bfsSeviye(ListeGraf* graf, int baslangic) {
    int V = graf->dugumSayisi;
    bool* ziyaret = calloc(V, sizeof(bool));
    Kuyruk* q = kuyrukOlustur(V);

    ziyaret[baslangic] = true;
    enqueue(q, baslangic);
    int seviye = 0;

    while (!kuyrukBos(q)) {
        int seviyeBoyut = q->son - q->bas;  // bu seviyedeki düğüm sayısı
        printf("Seviye %d: ", seviye);

        for (int i = 0; i < seviyeBoyut; i++) {
            int u = dequeue(q);
            printf("%d ", u);

            KomsulukNode* k = graf->listeler[u];
            while (k) {
                if (!ziyaret[k->hedef]) {
                    ziyaret[k->hedef] = true;
                    enqueue(q, k->hedef);
                }
                k = k->next;
            }
        }
        printf("\n");
        seviye++;
    }
}

Seviye 0: 0
Seviye 1: 1 2 3
Seviye 2: 4 5 6
Seviye 3: 7

/* En kısa yolu geri izle ve yazdır */
void enKisaYolYazdir(int ebeveyn[], int mesafe[],
                     int baslangic, int hedef) {
    if (mesafe[hedef] == -1) {
        printf("%d → %d: ulaşılamaz!\n", baslangic, hedef);
        return;
    }

    // Hedeften kaynağa doğru geri izle
    int yol[1000], uzunluk = 0;
    int curr = hedef;
    while (curr != -1) {
        yol[uzunluk++] = curr;
        curr = ebeveyn[curr];
    }

    // Ters çevirerek yazdır
    printf("%d → %d (mesafe: %d): ",
           baslangic, hedef, mesafe[hedef]);
    for (int i = uzunluk - 1; i >= 0; i--) {
        printf("%d", yol[i]);
        if (i > 0) printf(" → ");
    }
    printf("\n");
}

int main() {
    // Referans grafı oluştur (8 düğüm, yönsüz)
    ListeGraf* g = listeGrafOlustur(8, false);
    listeKenarEkle(g, 0, 1, 1);
    listeKenarEkle(g, 0, 2, 1);
    listeKenarEkle(g, 0, 3, 1);
    listeKenarEkle(g, 1, 4, 1);
    listeKenarEkle(g, 1, 2, 1);
    listeKenarEkle(g, 2, 5, 1);
    listeKenarEkle(g, 3, 6, 1);
    listeKenarEkle(g, 4, 7, 1);
    listeKenarEkle(g, 5, 7, 1);

    // BFS çalıştır
    int mesafe[8], ebeveyn[8];
    bfs(g, 0, mesafe, ebeveyn);

    // Sonuçları yazdır
    printf("=== BFS Sonuçları (kaynak: 0) ===\n");
    printf("Düğüm | Mesafe | Ebeveyn\n");
    printf("-------+--------+--------\n");
    for (int i = 0; i < 8; i++)
        printf("   %d   |   %d    |   %d\n",
               i, mesafe[i], ebeveyn[i]);

    // En kısa yolları yazdır
    printf("\n=== En Kısa Yollar ===\n");
    for (int hedef = 1; hedef < 8; hedef++)
        enKisaYolYazdir(ebeveyn, mesafe, 0, hedef);

    // Seviye seviye dolaşma
    printf("\n=== Seviye Seviye ===\n");
    bfsSeviye(g, 0);

    return 0;
}

=== BFS Sonuçları (kaynak: 0) ===
Düğüm | Mesafe | Ebeveyn
-------+--------+--------
   0   |   0    |   -1
   1   |   1    |    0
   2   |   1    |    0
   3   |   1    |    0
   4   |   2    |    1
   5   |   2    |    2
   6   |   2    |    3
   7   |   3    |    4

=== En Kısa Yollar ===
0 → 1 (mesafe: 1): 0 → 1
0 → 2 (mesafe: 1): 0 → 2
0 → 3 (mesafe: 1): 0 → 3
0 → 4 (mesafe: 2): 0 → 1 → 4
0 → 5 (mesafe: 2): 0 → 2 → 5
0 → 6 (mesafe: 2): 0 → 3 → 6
0 → 7 (mesafe: 3): 0 → 1 → 4 → 7

=== Seviye Seviye ===
Seviye 0: 0
Seviye 1: 1 2 3
Seviye 2: 4 5 6
Seviye 3: 7

int bagliBilesenSay(ListeGraf* graf) {
    int V = graf->dugumSayisi;
    bool* ziyaret = calloc(V, sizeof(bool));
    int bilesen = 0;

    for (int i = 0; i < V; i++) {
        if (!ziyaret[i]) {
            // Yeni bileşen! BFS ile hepsini ziyaret et
            int mesafe[V], ebeveyn[V];
            bfs(graf, i, mesafe, ebeveyn);

            // BFS'in ziyaret ettiği düğümleri işaretle
            for (int j = 0; j < V; j++)
                if (mesafe[j] != -1) ziyaret[j] = true;
            bilesen++;
        }
    }
    free(ziyaret);
    return bilesen;
}