Özet - BFS
- Algoritmalar kursu
- Orta seviye
- Ders 56/80
- 4 dk
Bir graph'ta BFS uygulayıp sırayı yazdıran mini görev yaparsın.
Özet - BFS
BFS; kuyruk, visited kümesi ve komşu döngüsüyle çalışan katman katman aramadır. En kısa adım sayısını verir.
Bu mini görevde BFS uygulayıp ziyaret sırasını yazdıracaksın; tüm parçaları birleştir.
BFS, ulaşılabilecek tüm düğümleri katman sırasıyla keşfeder; bu özellik shortest-path için idealdir.
Uygulama BFS yazdır
bfs_print(graph, start) yaz. BFS ziyaret sırasını print() ile yazdır. Çıktı: [0, 1, 2, 3].
Başlangıç kodu
def bfs_print(graph, start):
# BFS sırasını yazdırÖrnek çözüm
def bfs_print(graph, start):
# BFS sırasını yazdır
visited = []
queue = [start]
while queue:
node = queue.pop(0)
if node not in visited:
visited.append(node)
for nb in graph[node]:
if nb not in visited:
queue.append(nb)
print(visited)
bfs_print({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0)Beklenen çıktı
[0, 1, 2, 3]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Özet - BFS: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
BFS |
Kuyruk |
katman |
Adım |
visited |
Tekrar yok |
komşu |
Döngü |
2 Döngü koşulu
Soru
while ____:
Cevap
while queue:Açıklama: queue doğru.
3 BFS'nin zaman karmaşıklığı nedir?
- O(log V)
- O(V * E)
- O(V^2)
- O(V + E) Doğru cevap
Açıklama: O(V + E).