Genişlik Öncelikli Arama (BFS)

#Nasıl çalışır?

Genişlik öncelikli arama (Breadth-First Search, BFS), bir graftaki düğümleri başlangıç noktasına olan uzaklıklarına göre, katman katman gezer: önce tüm komşular, sonra komşuların komşuları, ve böyle devam eder.

Bu sırayı bir kuyruk (queue) sağlar: keşfedilen düğüm kuyruğun sonuna eklenir, sıradaki düğüm önden alınır. Bir düğümün iki kez eklenmemesi için "ziyaret edildi" kümesi tutulur.

Ağırlıksız bir grafta BFS'in bir düğümü ilk keşfettiği yol, o düğüme giden en kısa yoldur. Her düğümün nereden keşfedildiği (prev) kaydedilirse, yol hedeften geriye doğru izlenerek bulunur.

#Kendin dene

#Adım adım

1. 01Başlangıç düğümünü kuyruğa koy ve ziyaret edildi olarak işaretle.
2. 02Kuyruk boşalana kadar önden bir düğüm (u) al.
3. 03u'nun her komşusuna (v) bak; daha önce görülmediyse işaretle, prev[v] = u yaz ve kuyruğun sonuna ekle.
4. 04En kısa yol için: hedef kuyruktan çıktığında dur ve prev[] zincirini hedeften başlangıca doğru izle.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

from collections import deque

# Undirected graph as adjacency lists (neighbours in increasing order).
EDGES = [(1, 2), (1, 3), (2, 4), (2, 5), (3, 5), (3, 6), (4, 7), (5, 7), (6, 7)]
graph = {v: [] for v in range(1, 8)}
for a, b in EDGES:
    graph[a].append(b)
    graph[b].append(a)
for v in graph:
    graph[v].sort()


def bfs(start: int) -> list:
    order, visited, queue = [], {start}, deque([start])
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            if v not in visited:
                visited.add(v)  # mark when queued, so nothing is queued twice
                queue.append(v)
    return order


def shortest_path(start: int, target: int) -> list:
    prev, queue = {start: None}, deque([start])
    while queue:
        u = queue.popleft()
        if u == target:
            break
        for v in graph[u]:
            if v not in prev:
                prev[v] = u
                queue.append(v)
    if target not in prev:
        return []
    path = [target]
    while prev[path[-1]] is not None:
        path.append(prev[path[-1]])
    return path[::-1]


print(" ".join(map(str, bfs(1))))               # layer by layer
print(" ".join(map(str, shortest_path(1, 7))))  # fewest edges from 1 to 7

#Karmaşıklık

V düğüm, E kenar sayısıdır. Her düğüm kuyruğa en fazla bir kez girer ve her kenara iki uçtan birer kez bakılır. Kenarların ağırlıkları farklıysa BFS en kısa yolu bulamaz; o zaman Dijkstra gerekir.

#Ne zaman kullanılır?

Ağırlıksız grafta en kısa yol (labirent, oyun haritası, "kaç adımda" soruları), sosyal ağda arkadaşın arkadaşı önerileri, web tarayıcılarının sayfaları katman katman gezmesi, bir ağdaki yayılma (broadcast) ve iki parçalı (bipartite) graf kontrolü BFS ile yapılır.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.

#Bundan sonra

Bu dersi bildiğini varsayan dersler:

• Dijkstra Algoritması
• Topolojik Sıralama