🌳 3.6: BFS - Genişlik Öncelikli Arama

from collections import deque

def bfs(graf, baslangic):
    """
    BFS (Breadth-First Search) - Genişlik Öncelikli Arama

    Graf üzerinde başlangıç düğümünden başlayarak
    tüm ulaşılabilir düğümleri seviye seviye ziyaret eder.

    Parametreler:
        graf: Komşuluk listesi (dictionary)
        baslangic: Başlangıç düğümü

    Returns:
        Ziyaret edilen düğümlerin listesi (ziyaret sırasına göre)
    """
    # Ziyaret edilen düğümleri takip eden küme
    ziyaret_edildi = set()

    # Queue: İşlenecek düğümleri tutar (FIFO)
    kuyruk = deque([baslangic])

    # Başlangıcı ziyaret edildi olarak işaretle
    ziyaret_edildi.add(baslangic)

    # Ziyaret sırasını kaydet
    ziyaret_sirasi = []

    print(f"🚀 BFS Başlıyor - Başlangıç: {baslangic}")
    print("=" * 50)

    while kuyruk:  # Queue boş olana kadar devam et
        # Queue'dan (baştan) bir düğüm çıkar
        dugum = kuyruk.popleft()
        ziyaret_sirasi.append(dugum)

        print(f"📍 Ziyaret: {dugum}")
        print(f"   Kuyruk: {list(kuyruk)}")

        # Bu düğümün tüm komşularını kontrol et
        for komsu in graf[dugum]:
            if komsu not in ziyaret_edildi:
                # Henüz ziyaret edilmemişse kuyruğa ekle
                ziyaret_edildi.add(komsu)
                kuyruk.append(komsu)
                print(f"   ➕ Kuyruğa eklendi: {komsu}")

        print()

    return ziyaret_sirasi

# Örnek graf (komşuluk listesi)
graf = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print("📊 Graf Yapısı:")
for dugum, komsular in graf.items():
    print(f"   {dugum} → {komsular}")
print()

# BFS'i çalıştır
sonuc = bfs(graf, 'A')

print("=" * 50)
print(f"✅ Ziyaret Sırası: {' → '.join(sonuc)}")

from collections import deque

def bfs_en_kisa_yol(labirent, baslangic, hedef):
    """
    2D labirentte BFS ile en kısa yolu bulur.

    Labirent:
        0 = geçilebilir hücre
        1 = duvar

    Returns:
        En kısa yol (koordinat listesi) veya None
    """
    satirlar = len(labirent)
    sutunlar = len(labirent[0])

    # 4 yön: yukarı, aşağı, sol, sağ
    yonler = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    # Queue: (satir, sutun, yol)
    kuyruk = deque([(baslangic[0], baslangic[1], [baslangic])])

    # Ziyaret edilen hücreler
    ziyaret_edildi = {baslangic}

    while kuyruk:
        satir, sutun, yol = kuyruk.popleft()

        # Hedefe ulaştık mı?
        if (satir, sutun) == hedef:
            return yol

        # 4 yöne bak
        for ds, dc in yonler:
            yeni_satir = satir + ds
            yeni_sutun = sutun + dc
            yeni_konum = (yeni_satir, yeni_sutun)

            # Sınırlar içinde mi?
            if 0 <= yeni_satir < satirlar and 0 <= yeni_sutun < sutunlar:
                # Duvar değil mi ve ziyaret edilmemiş mi?
                if labirent[yeni_satir][yeni_sutun] == 0 and yeni_konum not in ziyaret_edildi:
                    ziyaret_edildi.add(yeni_konum)
                    kuyruk.append((yeni_satir, yeni_sutun, yol + [yeni_konum]))

    return None  # Yol bulunamadı

# Örnek labirent
# S = Start (Başlangıç), E = End (Hedef)
# 0 = Geçilebilir, 1 = Duvar
labirent = [
    [0, 0, 0, 1, 0],  # S . . # .
    [1, 1, 0, 1, 0],  # # # . # .
    [0, 0, 0, 0, 0],  # . . . . .
    [0, 1, 1, 1, 0],  # . # # # .
    [0, 0, 0, 0, 0],  # . . . . E
]

baslangic = (0, 0)  # Sol üst köşe
hedef = (4, 4)      # Sağ alt köşe

print("🗺️ Labirent (0=yol, 1=duvar):")
for i, satir in enumerate(labirent):
    satir_str = ""
    for j, hucre in enumerate(satir):
        if (i, j) == baslangic:
            satir_str += "S "
        elif (i, j) == hedef:
            satir_str += "E "
        elif hucre == 1:
            satir_str += "█ "
        else:
            satir_str += ". "
    print(f"   {satir_str}")

print()

# En kısa yolu bul
yol = bfs_en_kisa_yol(labirent, baslangic, hedef)

if yol:
    print(f"✅ En kısa yol bulundu! ({len(yol)-1} adım)")
    print(f"   Yol: {' → '.join([str(k) for k in yol])}")

    # Yolu labirent üzerinde göster
    print("\n🎯 Çözüm:")
    for i, satir in enumerate(labirent):
        satir_str = ""
        for j, hucre in enumerate(satir):
            if (i, j) == baslangic:
                satir_str += "S "
            elif (i, j) == hedef:
                satir_str += "E "
            elif (i, j) in yol:
                satir_str += "* "
            elif hucre == 1:
                satir_str += "█ "
            else:
                satir_str += ". "
        print(f"   {satir_str}")
else:
    print("❌ Yol bulunamadı!")