Ağırlıksız En Kısa Yollar için BFS
Bir kaynaktan katman katman uzaklık hesaplayın.
Ağırlıksız En Kısa Yollar için BFS, CoddyKit'te ücretsiz bir Competitive Programming Academy dersidir. Bu, 4 dersinin 2. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Competitive Programming Academy öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Competitive Programming Academy kursu toplamda 4 dersten oluşur.
BFS Ne Yapar
BFS bir grafiği halkalar halinde gezer: önce başlangıç düğümünüzü, sonra bir adım uzaktaki her şeyi, ardından iki adım uzaktakileri ve devamını ziyaret eder. 🌊
Halkalar Neden En Kısa Yolu Verir
BFS sonraki halkaya geçmeden önce mevcut halkayı tamamen bitirdiği için bir düğüme ilk ulaştığı an, o düğüme giden en kısa ağırlıksız yol bulunmuş olur.
Kuyruk İşlemin Motorudur
BFS bir kuyruk kullanır: ilk giren ilk çıkar. Yeni komşuları arkaya eklersiniz ve sıradaki öndekini işlersiniz.
from collections import deque
q = deque([start])Ziyaret Ettiklerinizi Takip Edin
Aynı düğümü iki kez kuyruğa eklememek için bir ziyaret edildi işareti tutun. Bu, BFS'nin hızlı ve sonlu kalmasını sağlar.
visited = [False] * (n + 1)
visited[start] = TrueUzaklığı Saklayın
Bir uzaklık dizisi her düğümün katmanını tutar. Başlangıç düğümünün değeri 0'dır; her komşunun değeri, üst düğümünün değerinden bir fazladır.
dist = [-1] * (n + 1)
dist[start] = 0Öndekini Kuyruktan Çıkarın
Her adımda kuyruğun önündeki düğümü alın. Bu, işlenmemiş en yakın düğümdür; dolayısıyla şimdi onu ele alın.
u = q.popleft()Komşuları Genişletin
Ziyaret edilmemiş her komşu için onu işaretleyin, uzaklığını ayarlayın ve kuyruğun arkasına ekleyin.
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)Tam Döngü
Kuyruk boş olmadığı sürece düğümleri kuyruktan çıkarıp komşuları genişletmeye devam edin. Kuyruk tükendiğinde erişilebilen her düğümü ziyaret etmiş olursunuz.
while q:
u = q.popleft()
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)Kuyruğa Eklerken İşaretleyin
Ziyaret edildi durumunu düğümü kuyruktan çıkardığınızda değil, kuyruğa eklediğiniz anda ayarlayın. Geç işaretlemek, kopyaların kuyruğa girmesine izin verir.
Erişilemeyenler -1 Olarak Kalır
BFS sonrasında uzaklığı hâlâ -1 olan herhangi bir düğüm, başlangıç noktanızdan erişilemez durumdadır. Bu da anlamlı bir sonuçtur.
BFS Doğrusaldır
BFS her düğüme ve kenara bir kez dokunduğu için O(n + m) zamanda çalışır. Bu karmaşıklık çoğu yarışma zaman sınırını rahatça karşılar.
Hızlı Kontrol
Sıradan BFS neden en kısa yolları verir?
Özet
BFS'yi bir kuyruk ve uzaklık dizisiyle çalıştırırsınız: kuyruğa eklerken işaretler, komşuları genişletir ve bittiğinde en kısa uzaklıkları okursunuz. 🎉
Sıkça Sorulan Sorular
“Ağırlıksız En Kısa Yollar için BFS” dersi ücretsiz mi?
Evet — “Ağırlıksız En Kısa Yollar için BFS” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Competitive Programming Academy kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Competitive Programming Academy kursu toplamda 4 dersten oluşur.
“Ağırlıksız En Kısa Yollar için BFS” dersinde ne öğreneceğim?
Bir kaynaktan katman katman uzaklık hesaplayın. Competitive Programming Academy ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
Competitive Programming Academy öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Competitive Programming Academy, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 2. dersidir.
“Ağırlıksız En Kısa Yollar için BFS” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu Competitive Programming Academy dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Competitive Programming Academy dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- Girdiden Komşuluk Listeleri
- Ağırlıksız En Kısa Yollar için BFS
- DFS, Özyineleme ve Yinelemeli Yığınlar
- Bağlantılı Bileşenler ve Taşma Doldurma