Deque ile 0-1 BFS
Ağırlıkların 0 veya 1 olduğu durumlarda en kısa yolları bulun.
Deque ile 0-1 BFS, CoddyKit'te ücretsiz bir Coding Interview Prep 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, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.
Özel Bir Graf Türü
Bazı graflarda yalnızca 0 veya 1 kenar ağırlıkları bulunur. Bu durumda Dijkstra'yı daha basit ve hızlı bir yöntemle geride bırakabilirsiniz.
0-1 BFS ile Tanışın
0-1 BFS, 0/1 ağırlıklı graflarda yığın kullanmadan ve hiçbir logaritma çarpanı olmadan, en kısa yolları doğrusal sürede bulur.
Araç: Çift Uçlu Kuyruk
Yığın yerine, hem önüne hem de arkasına ekleme ve her iki uçtan çıkarma yapabildiğiniz bir çift uçlu kuyruk kullanın.
from collections import deque
dq = deque([src])Temel İçgörü
0 ağırlıklı bir kenar uzaklığı değiştirmez, 1 ağırlıklı bir kenar ise uzaklığa bir ekler. Çift uçlu kuyruk her iki grubu da sıralı tutar.
Sıfır Kenarlar İçin Ön Taraf
0 ağırlıklı bir kenarı geçtiniz mi? Komşuyu appendleft ile ekleyin; ek bir uzaklık maliyeti olmadığı için sırada o işlenir.
dq.appendleft(v)Bir Kenarlar İçin Arka Taraf
1 ağırlıklı bir kenarı geçtiniz mi? Komşuyu arkaya append ile ekleyin; çünkü kaynak düğümden bir katman daha uzaktadır.
dq.append(v)Önden Çıkarın
Her zaman mevcut düğümü popleft ile çıkarın. Bu, katmanlı bir BFS'de olduğu gibi çift uçlu kuyruğu uzaklığa göre sıralı tutar.
u = dq.popleft()Ağırlıkla Gevşetin
Her kenarı gevşetin: yeni uzaklık dist[u] ile kenar ağırlığının toplamıdır; ardından ağırlığa göre ön tarafa veya arka tarafa ekleyin.
nd = dist[u] + w
if nd < dist[v]:
dist[v] = ndSıralı Kalmasının Nedeni
Çift uçlu kuyruk aynı anda en fazla iki farklı uzaklık tutar. Bu değişmez, ön ve arka tarafa eklemenin neden işe yaradığını açıklar.
Doğrusal Hız
Yığın kullanılmadığı için 0-1 BFS O(V + E) sürede çalışır; aynı graf üzerinde Dijkstra'dan belirgin biçimde hızlıdır.
Ne Zaman Kullanılmalı
Hareketlerin ücretsiz veya maliyetinin bir olduğu her durumda kullanın; örneğin bazı adımların kapalı, bazılarının açık olduğu ızgaralarda.
Hızlı Kontrol
Ağırlığı 0 olan bir kenar üzerinden bir komşuyu gevşetiyorsunuz. Bu komşu nereye gider?
Özet: 0-1 BFS
Bir çift uçlu kuyrukla 0 ağırlıklı kenarları öne, 1 ağırlıklı kenarları arkaya ekleyin. O(V+E) gibi temiz bir sürede en kısa yolları elde edersiniz. ⚡
Sıkça Sorulan Sorular
“Deque ile 0-1 BFS” dersi ücretsiz mi?
Evet — “Deque ile 0-1 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 Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.
“Deque ile 0-1 BFS” dersinde ne öğreneceğim?
Ağırlıkların 0 veya 1 olduğu durumlarda en kısa yolları bulun. Coding Interview Prep 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.
Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, 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.
“Deque ile 0-1 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 Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Coding Interview Prep 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.