BFS ile bağlantı
- Algoritmalar kursu
- Orta seviye
- Ders 75/80
- 4 dk
BFS ile hangi şehirlere ulaşılabilir bulursun.
BFS ile bağlantı
Şimdi BFS ile bir şehirden hangi şehirlere ulaşılabileceğini bulacağız. Tüm ulaşılabilir şehirleri keşfet.
BFS, kuyruk ve visited kümesiyle çalışır; katman katman yayılır.
Sonuç olarak ulaşılabilir şehirlerin sıralı listesini döndüreceğiz; çıktı deterministik olsun.
Sorted çıktı
Sonuçları sorted() ile sıralayarak deterministik çıktı elde ederiz; her çalıştırma aynı sonucu verir.
BFS çıktısı zaten deterministiktir ama sıralama ek garanti sağlar; test için önemlidir.
Sıralı liste, çıktıyı okunabilir kılar; şehirler alfabetik sıralanır.
Uygulama Ulaşılabilir şehirler
bfs_reachable(graph, start) yaz. BFS ile ulaşılabilecek şehirleri sıralı liste olarak döndür. print(bfs_reachable(build_cities(), "A")) ile ['A', 'B', 'C', 'D'] yazdır.
Başlangıç kodu
def build_cities():
# Şehir graph'ını tanımla
return {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"], "D": ["B", "C"]}
def add_neighbor(graph, city, neighbor):
# Komşu ekle
graph[city].append(neighbor)
return graph
def bfs_reachable(graph, start):
# Ulaşılabilir şehirlerÖrnek çözüm
def build_cities():
# Şehir graph'ını tanımla
return {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"], "D": ["B", "C"]}
def add_neighbor(graph, city, neighbor):
# Komşu ekle
graph[city].append(neighbor)
return graph
def bfs_reachable(graph, start):
# Ulaşılabilir şehirler
visited = set()
queue = [start]
while queue:
node = queue.pop(0)
if node not in visited:
visited.add(node)
for nb in graph[node]:
if nb not in visited:
queue.append(nb)
return sorted(visited)
print(bfs_reachable(build_cities(), "A"))Beklenen çıktı
['A', 'B', 'C', 'D']
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Kuyruk başlatma
queue = [____]queue = [start]Açıklama: start doğru.
2 BFS ile bağlantı: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
BFS |
Katman |
queue |
Kuyruk |
visited |
Tekrar yok |
sorted |
Alfabetik |
3 BFS çıktısını sıralamak ne sağlar?
- Daha hızlı çalışma
- Deterministik sonuç Doğru cevap
- Daha az kenar
- Daha az bellek
Açıklama: Deterministik sonuç.