Meydan okuma 3
- Algoritmalar kursu
- Orta seviye
- Ders 79/80
- 4 dk
Bir graph'ta BFS uygulayıp sırayı yazdırırsın.
Meydan okuma 3: BFS
Bu meydan okumada bir graph'ta BFS uygulayıp ziyaret sırasını yazdıracaksın.
Graph: {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}. Kaynak: 0. Çıktı: [0, 1, 2, 3].
BFS; kuyruk ve visited kümesiyle katman katman gezer; en kısa adım sayısını verir.
Uygulama BFS yazdır
bfs_order(graph, start) yaz. BFS ziyaret sırasını yazdır. Çıktı: [0, 1, 2, 3].
Başlangıç kodu
def bfs_order(graph, start):
# BFS sırasını yazdırÖrnek çözüm
def bfs_order(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_order({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 Meydan okuma 3: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
BFS |
Katman |
queue |
Kuyruk |
visited |
Tekrar yok |
O(V+E) |
Hızlı |
2 BFS hangi veri yapısını kullanır?
- Kuyruk Doğru cevap
- Heap
- Yığın
- Trie
Açıklama: Kuyruk.
3 Döngü koşulu
Soru
while ____:
Cevap
while queue:Açıklama: queue doğru.