Genişlik Öncelikli Arama - Seviye Seviye Keşfetmek
BFS (Breadth-First Search), bir grafı seviye seviye dolaşan bir algoritmadır. Başlangıç düğümünden başlar, önce tüm komşularını ziyaret eder, sonra komşuların komşularını... Tıpkı suya atılan bir taşın yarattığı dalgalar gibi yayılır!
Düşünün: Sakin bir göle taş attınız. Dalgalar merkezdeki taştan başlayarak eş merkezli halkalar halinde yayılır. BFS de tam olarak böyle çalışır:
FIFO (First In, First Out) yapısı sayesinde düğümler keşfedildiği sırada işlenir. Bu da seviye sırasının korunmasını sağlar!
Stack kullansaydık? O zaman DFS olurdu! 😉
Başlangıç düğümü: A
📥 Queue (Kuyruk)
✅ Ziyaret Sırası
from collections import deque
def bfs(graph, start):
"""
Breadth-First Search (BFS) - Genişlik Öncelikli Arama
Args:
graph: Adjacency list formatında graf (dict)
start: Başlangıç düğümü
Returns:
Ziyaret sırası listesi
"""
visited = set() # Ziyaret edilenler (tekrar ziyareti önler)
queue = deque([start]) # İşlenecek düğümler kuyruğu
visited.add(start) # Başlangıcı hemen işaretle!
result = [] # Ziyaret sırası
while queue:
# Queue'nun başından al (FIFO)
current = queue.popleft()
result.append(current)
print(f"Ziyaret: {current}, Queue: {list(queue)}")
# Tüm komşulara bak
for neighbor in graph[current]:
if neighbor not in visited:
visited.add(neighbor) # Hemen işaretle!
queue.append(neighbor)
print(f" → {neighbor} eklendi")
return result
# Test graf
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
print("Graf:")
for node, neighbors in graph.items():
print(f" {node}: {neighbors}")
print("\n=== BFS A'dan Başlayarak ===\n")
result = bfs(graph, 'A')
print(f"\n✅ Ziyaret sırası: {result}")BFS'in en önemli özelliği: Ağırlıksız graflarda en kısa yolu bulur! Çünkü düğümleri seviye sırasında ziyaret eder ve bir düğüme ilk ulaşıldığında o düğüme en az kenarla ulaşılmış demektir.
from collections import deque
def bfs_shortest_path(graph, start, goal):
"""
BFS ile en kısa yolu bul (ağırlıksız graf)
Her düğüm için "parent" (önceki düğüm) kaydederiz.
Hedefe ulaşınca parent'ları takip ederek yolu oluştururuz.
"""
if start == goal:
return [start]
visited = {start}
queue = deque([start])
# Her düğümün parent'ını tut
parent = {start: None}
while queue:
current = queue.popleft()
for neighbor in graph[current]:
if neighbor not in visited:
visited.add(neighbor)
parent[neighbor] = current
queue.append(neighbor)
# Hedefe ulaştık mı?
if neighbor == goal:
# Yolu oluştur (geriye doğru git)
path = []
node = goal
while node is not None:
path.append(node)
node = parent[node]
return path[::-1] # Ters çevir
return None # Yol yok
# Test
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E'],
'G': ['H'], # Bağlantısız bileşen
'H': ['G']
}
print("=== EN KISA YOL ===\n")
# Test 1: A'dan F'ye
path = bfs_shortest_path(graph, 'A', 'F')
print(f"A → F: {' → '.join(path)}")
print(f"Mesafe: {len(path) - 1} kenar\n")
# Test 2: D'den F'ye
path = bfs_shortest_path(graph, 'D', 'F')
print(f"D → F: {' → '.join(path)}")
print(f"Mesafe: {len(path) - 1} kenar\n")
# Test 3: A'dan G'ye (ulaşılamaz)
path = bfs_shortest_path(graph, 'A', 'G')
print(f"A → G: {path} (Farklı bileşende!)")BFS (veya DFS) ile bir grafın bağlantılı bileşenlerini bulabiliriz. Her bileşen, birbiriyle yol ile bağlı düğümler kümesidir.
from collections import deque
def find_connected_components(graph):
"""
Grafın tüm bağlantılı bileşenlerini bul
Returns:
Bileşenlerin listesi (her biri düğümler kümesi)
"""
visited = set()
components = []
def bfs_component(start):
"""Tek bir bileşeni BFS ile bul"""
component = []
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft()
component.append(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return component
# Her düğümü kontrol et
for node in graph:
if node not in visited:
# Yeni bileşen bulundu!
component = bfs_component(node)
components.append(component)
return components
# Test: 3 bileşenli graf
graph = {
# Bileşen 1: A-B-C-D
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A'],
'D': ['B'],
# Bileşen 2: E-F
'E': ['F'],
'F': ['E'],
# Bileşen 3: G (izole)
'G': []
}
print("=== BAĞLANTILI BİLEŞENLER ===\n")
components = find_connected_components(graph)
for i, comp in enumerate(components, 1):
print(f"Bileşen {i}: {sorted(comp)}")
print(f"\nToplam {len(components)} bileşen bulundu!")
# Pratik: Sosyal ağ analizi
print("\n=== SOSYAL AĞ ÖRNEĞİ ===")
print("Her bileşen bir 'arkadaş grubu' gibi düşünülebilir.")
print("Birbiriyle bağlantısı olmayan gruplar farklı 'ada'lardır.")| Metrik | Karmaşıklık | Açıklama |
|---|---|---|
| Zaman | O(V + E) | Her düğüm 1 kez, her kenar 2 kez işlenir |
| Alan | O(V) | Queue + visited set için |
Ağırlıksız graflarda en kısa yol. Google Maps'te "en az durak" hesaplamalarında.
"6 derece ayrımı" - iki kişi arasındaki en kısa arkadaş zinciri. LinkedIn bağlantı derecesi.
Arama motorları sayfaları BFS ile tarar. Başlangıç sayfasından tüm linkleri keşfeder.
Rubik küpü, 15-puzzle gibi oyunlarda minimum hamle sayısını bulma.
Bir mesajı ağdaki tüm düğümlere yaymak için BFS benzeri yayılım.
Bir karakterin labirentte en kısa çıkış yolunu bulması.
| Özellik | BFS | DFS |
|---|---|---|
| Veri Yapısı | Queue (FIFO) | Stack (LIFO) / Recursion |
| Arama Şekli | Seviye seviye (genişlik) | Dal dal (derinlik) |
| En Kısa Yol | ✅ Garanti (ağırlıksız) | ❌ Garanti değil |
| Bellek | O(V) - geniş graflarda fazla | O(h) - derinlik kadar |
| Kullanım | En kısa yol, seviye analizi | Döngü tespiti, topolojik sıralama |