Özet - BFS

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].

Örnek çözümü göster

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)

Kendini test et

Özet - BFS: kavramları eşleştir

BFS

Kuyruk
katman

Adım
visited

Tekrar yok
komşu

Döngü
Döngü koşulu
```
while ____:
```
Cevabı göster
```
while queue:
```
BFS'nin zaman karmaşıklığı nedir?
- O(log V)
- O(V * E)
- O(V^2)
- O(V + E)
Cevabı göster

O(V + E) — O(V + E).

Sıradaki ders: DFS mantığı

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler