Konuşma notu: Bir ağaçta bir düğüm birden çok çocuğa işaret edebiliyordu, ama asla geriye ya da yana dönemiyordu. Bu iki kısıtı da kaldırın -- herhangi bir düğüm herhangi bir düğüme işaret edebilsin -- ağaç bir ÇİZGEYE (graph) dönüşür, bu dersteki en genel şekle.
Konuşma notu: Sekiz kısa animasyon dersin tamamını taşıyor; her biri fikrin tanıtıldığı yerde tam olarak bir kez görünüyor ve her biri zor ya da uç bir girdiyle ikinci kez ele alınıyor.
Konuşma notu: Her terim ilk geçtiği yerde tam tanımlanır; bu tablo yalnızca onu tekrar nerede bulacağınızı söylüyor.
Konuşma notu: Canlı çalıştırmak isterseniz şimdi bir terminal açın; bugünkü her slaytın kodu tam gösterildiği gibi derlenir ve çalışır.
Konuşma notu: Mekanizmada yeni hiçbir şey yok -- bu iki yapının tuttuğu veri için yeni bir şekil var, o kadar.
Konuşma notu: Geçen haftaki "n düğüm, n-1 kenar, döngü yok" kuralı özel bir durumdu; bugün bu kısıt tamamen kalkıyor.
Konuşma notu: Bu haritadaki her kutunun kendi slaytları var, çoğunda kısa bir animasyon ve eksiksiz bir C/Java programı var.
Konuşma notu: Bölüm 1, çizge teorisinin en eski problemiyle bütün haftayı motive ediyor, sonra aynı şeklin haritalarda, arkadaşlıklarda ve web'de nasıl saklandığını gösteriyor.
Konuşma notu: Bu, 1700'lerde küçük bir şehrin kendine sorduğu gerçek bir soru -- ve matematiğe tamamen yeni bir dal kazandırdı.
Konuşma notu: Euler makalesinde tek bir köprü bile çizmedi -- hangi kara parçasının hangisine bağlı olduğu dışında her şeyi attı, ki bu tam olarak bir çizge fikridir.
Konuşma notu: Haritayı atıp yalnızca "neyin neye bağlı olduğunu" tutmak, bu dersteki en önemli tek hamledir.
Konuşma notu: Bu tek sayma argümanı, derece paritesi, yanıtın yalnızca o şehir için değil, Königsberg gibi şekillenmiş her şehir için "hayır" olmasının nedenidir.
Konuşma notu: "Düğümler ve kenarlar", bilgisayar biliminin en tekrar kullanılabilir fikirlerinden biri olduğunu kanıtladı.
Konuşma notu: Bastığınız her "yol tarifi al" düğmesinin altında bir çizge en kısa yol algoritmasının bir biçimi çalışıyordu.
Konuşma notu: Bir arkadaş önerisi özelliği, altta neredeyse her zaman kendi düğümünüzden kısa bir genişlik öncelikli aramadır.
Konuşma notu: PageRank, Google'ın özgün sıralama fikri, temelde tam olarak bu yönlü bağlantı çizgesi üzerinde yapılan bir hesaplamadır.
Konuşma notu: Bu tabloyu haftanın geri kalanı boyunca aklınızda tutun -- aşağıdaki her dolaşma fikri, bu üç kısıt kaldırılmış bir ağaç fikridir.
Konuşma notu: Bugünün her algoritması, bu slaytın listelediği tuhaf durumlarda da doğru çalışmalı -- aşağıdaki "uç durum" animasyonları tam olarak bunu sınıyor.
Konuşma notu: Birkaç slayt önceki parite kuralını uygulayın.
Konuşma notu: Sıfır tek düğüm başlangıca dönen bir tur verir; tam olarak iki düğüm tek yönlü bir yürüyüş verir -- başka her durumda hiç yürüyüş yoktur.
Konuşma notu: Bölüm 2, sonraki her bölümün dayandığı terimleri kuruyor -- düğüm, kenar, derece, yol, döngü -- hepsi tek bir işlenmiş örnek üzerinde.
Konuşma notu: Neredeyse her şey -- şaşırtıcı biçimde, bu iki kümelik tanım bütün temeldir.
Konuşma notu: Bu biçimsel tanım kasıtlı olarak yalın görünüyor -- gücü, tam olarak ne kadar az varsayım yapmasından geliyor.
Konuşma notu: Bunların her biri, bu tablodan hemen sonraki animasyonda birer birer işaret ediliyor.
Konuşma notu: Ağırlıksız bir kenar aslında ağırlığı hep 1 olan ağırlıklı bir kenardır.
Konuşma notu: Derece ancak yön varsa ikiye ayrılır -- yönsüz bir çizgede "gelen" ya da "giden" hiç gerekmez.
Konuşma notu: Öz-döngüye ve çoklu kenara izin veren bir çizgeye bazen özellikle MULTIGRAPH denir.
Konuşma notu: Bu ayrım, Bölüm 3'te bir çizgeyi nasıl saklayacağınızı seçerken çok önemli oluyor.
Konuşma notu: Bu haftaki her algoritma, tekrar tekrar sorulan bu üç küçük soru üzerine kuruludur.
Konuşma notu: Normal örnek: 8 düğüm, ağırlıklı, bir döngü, bir öz-döngü, bir çoklu kenar ve 2 bileşenle -- bu bölümün her terimi, tek bir çizge üzerinde.
Konuşma notu: 8 düğüm, yönlü, iki ayrı döngü, bir öz-döngü, bir çoklu kenar ve 2 zayıf bileşenle -- artık gelen derece ile giden derece düğüm başına gerçekten farklılaşıyor.
Konuşma notu: Bir kenar için bir yapı, bütün çizge için bir yapı -- bu haftaki her algoritma tam olarak bu iki şekil üzerine kurulu.
Konuşma notu: Yönsüz bir çizgede bu tek fonksiyon bir düğümün ihtiyacı olan her şeyi zaten sayar -- ayrı bir "gelen" sürümü gerekmez.
Konuşma notu: v'ye kimin işaret ettiğini bulmak, DİĞER her düğümün listesini taramak demek -- ek bir kayıt tutmadan bir kısayol yok.
Konuşma notu: Bu asimetri, yalnızca giden kenarları saklama seçiminin doğrudan bir sonucudur -- Bölüm 3'ün açıkladığı komşuluk listesi seçimi.
Konuşma notu: Yukarıdaki zor ön ayar animasyonu, özellikle çoğu düğümde gelen ve giden derecenin farklılaşması için kuruldu.
Konuşma notu: Bir öz-döngünün tek kenarının hangi yöne "işaret ettiğini" düşünün.
Konuşma notu: Yönsüz bir çizgede aynı öz-döngü düz dereceyi 1 değil 2 artırır -- yön sayma kuralını değiştiriyor.
Konuşma notu: Çizge bir fikirdir; bir programın onu saklayacak somut bir yola ihtiyacı var. Bu bölüm iki standart seçimi, aynı çizgeler üzerinde, yan yana kuruyor.
Konuşma notu: Tek bir en iyi yanıt yok -- aşağıdaki iki yapı, birinin hızını diğerinin belleğiyle takas ediyor.
Konuşma notu: Aşağıdaki iki bölüm, bunları tam olarak aynı kenar listelerinden kuruyor, böylece iki gösterim doğrudan karşılaştırılabiliyor.
Konuşma notu: Yönsüz bir çizgenin matrisi her zaman köşegene göre simetriktir -- bu simetri, "her iki yön"ün sayı olarak ifadesidir.
Konuşma notu: Normal örnek: 7 düğüm, yönsüz, ağırlıksız, 10 kenar -- matrisin simetrik hücre çiftleri halinde dolduğunu izleyin.
Konuşma notu: 5 düğüm, her çift bağlı, 10 kenar -- 5 düğüm için mümkün olan en fazlası, ve matris köşegen dışında tamamen doluyor.
Konuşma notu: Yönlü bir kenar için bir atama, yönsüz için -- aynalanmış -- iki atama; tüm fark bu tek "if".
Konuşma notu: Önce bütün tabloyu sıfırla, sonra kenarları teker teker ekle -- sıra önemli değil, her kenar yalnız kendi iki hücresine dokunur.
Konuşma notu: Matrisin maliyeti kaç kenarın gerçekten var olduğuna değil, kaç düğümün mümkün olabileceğine bağlıdır.
Konuşma notu: Bu, Hafta 2'nin tam olarak aynı bağlı liste düğümü, yeniden kullanılmış: bir alan komşunun kimliği için, bir alan "sonraki" için.
Konuşma notu: Matrisle aynı normal örnek: 7 düğüm, yönsüz, ağırlıksız, 10 kenar -- her kenarın bir ya da iki listeye eklenmesini izleyin.
Konuşma notu: 8 düğüm, yönlü, ağırlıklı, ters bir çift `P>R` ve `R>P` dahil 10 kenar -- bazı düğümlerin listesi tamamen boş kalıyor, hiç giden kenarı olmadığı için.
Konuşma notu: Tam olarak Hafta 2'nin tek yönlü bağlı liste eklemesi: sona kadar yürü, sonra ekle -- çizgeler bu kalıpta hiçbir şeyi değiştirmiyor.
Konuşma notu: `a != b` öz-döngü kontrolü, yönsüz bir öz-döngünün aynı listeye iki kez eklenmemesi için var.
Konuşma notu: has_edge, matrisin kesinlikle kazandığı tek işlem -- liste aramak zorunda, matris hiç aramaz.
Konuşma notu: Üç satır, ve sonraki her algoritmanın karmaşıklığı doğrudan bu küçük tabloya dayanıyor.
Konuşma notu: Bu dersin gerçekten önemsediği çizgeler için yakın bir karar bile değil -- liste açık farkla kazanıyor.
Konuşma notu: İki yapı da tam olarak aynı bilgiyi saklıyor -- bu seçim tamamen bir mühendislik takası, asla bir doğruluk meselesi değil.
Konuşma notu: Yönlü bir matrisin iki "ayna" hücresi, matrix[a][b] ve matrix[b][a], gerçekten birbirinden tamamen farklı iki değer tutabilir.
Konuşma notu: Düğüm sayısının karesini alın, sonra kenar sayısıyla karşılaştırın.
Konuşma notu: Bu tam olarak Bölüm 3'ün "seyrek mi yoğun mu" kuralının yazıldığı durum.
Konuşma notu: BFS, Hafta 4'ün seviye sırasının bir ağaçtan herhangi bir çizgeye genelleşmiş hali -- tek başına bir kuyruk bütün algoritmayı yürütüyor.
Konuşma notu: "En yakından başlayarak" fikrin tamamı; aşağıdaki algoritma tam olarak bu sırayı garanti etmek için kurulu.
Konuşma notu: Moore fiziksel bir labirent kablolama sorununu çözüyordu -- aynı kuyruk tabanlı fikir her çizgeye genelleşti.
Konuşma notu: Hiçbir dalga bir öncekini geçmez -- bu sıralama garantisi, BFS'nin en kısa yolu bulmasını sağlayan tam olarak budur.
Konuşma notu: BFS ağacı, her düğüm için, ona ilk ulaşan tam olarak bir kenarı kaydeder -- bu, Bölüm 8'in yeniden kullandığı ebeveyn işaretçisidir.
Konuşma notu: Normal örnek: 7 düğüm, yönsüz, A'dan başlıyor, 10 kenar -- kuyruğun ve seviye[] satırının birlikte dolmasını izleyin.
Konuşma notu: 9 düğüm, 2 bileşen -- G, H, I başlangıç düğümü A'dan basitçe erişilemez ve bütün çalışma boyunca gri kalırlar.
Konuşma notu: Hafta 3'ün tam olarak aynı dairesel kuyruğu -- yalnızca eleman türü değişti, int puanlardan çizge düğüm kimliklerine.
Konuşma notu: Ziyaret edilmemiş her komşu, kuyruğa eklendiği anda işaretlenir, seviyelendirilir ve bir ebeveyn işaretçisi kazanır.
Konuşma notu: Bu O(V + E) sınırı, çizge algoritmalarındaki en yaygın karmaşıklık sonucu, ve bu hafta boyunca tekrar tekrar karşımıza çıkıyor.
Konuşma notu: BFS aslında zaten ağırlıksız en kısa yol problemini çözüyor; Bölüm 8 yalnızca bu gerçeği açıkça ortaya koyuyor.
Konuşma notu: Soru "ağırlıklı en kısa mesafe" değil de "en az adım" olduğunda, BFS genellikle başvurulacak ilk doğru araçtır.
Konuşma notu: "Ziyaret edildi" işaretini çok geç koymak, en yaygın BFS hatasıdır -- aynı düğüm birden fazla kez eklenebilir.
Konuşma notu: Birkaç slayt önce "seviye"nin tam olarak ne anlama geldiğini hatırlayın.
Konuşma notu: Bu, Bölüm 8'in tam bir algoritmaya dönüştürdüğü gerçek: seviye, ağırlıksız çizgeler için en kısa yol uzunluğunun TA KENDİSİDİR.
Konuşma notu: DFS, Hafta 4'ün ön sırasının bir ağaçtan herhangi bir çizgeye genelleşmiş hali -- tek başına özyineleme bütün algoritmayı yürütüyor.
Konuşma notu: "Bağlan, sonra geri dön", derinlik öncelikli aramayı tek cümlede anlatır -- BFS'in halka halka yaklaşımının tam tersi bir strateji.
Konuşma notu: Özyineleme aslında bir yığındır, Hafta 3'ten -- her özyinelemeli dfs_visit çağrısı bir çerçeve ekler, her dönüş bir çerçeve çıkarır.
Konuşma notu: Bir düğüm, çağrı yığınında olduğu sürece grıdir -- döndüğü an siyaha döner.
Konuşma notu: İleri ve çapraz kenarlar yönsüz bir çizgede oluşamaz -- orada bulunan her ağaç-dışı kenar bir geri kenardır.
Konuşma notu: Normal örnek: 7 düğüm, yönsüz, 4 geri kenar, 10 kenar -- çağrı yığını sütununun ve disc/fin[]'in birlikte dolmasını izleyin.
Konuşma notu: 6 düğüm, yönlü, özellikle bir ağaç, bir geri, bir ileri ve bir çapraz kenarın hepsinin tek bir çalışmada görünmesi için kurulmuş.
Konuşma notu: Tek paylaşılan bir saat, hem her keşifte hem her bitişte ilerler -- disc/fin aralıklarının doğru iç içe geçmesini sağlayan budur.
Konuşma notu: Üç renk, üç dal -- birkaç slayt önceki kenar sınıflama fikrinin tamamı, tek bir if/else zinciri olarak.
Konuşma notu: Bağlı olmayan bir çizgenin DFS'i tek bir ağaç değil bir DFS ORMANI üretir -- bileşen başına bir ağaç, tam olarak Bölüm 7'nin bileşenleri gibi.
Konuşma notu: BFS ve DFS tam olarak aynı düğüm ve kenar kümesini ziyaret eder -- yalnızca SIRA değişir, toplam iş asla.
Konuşma notu: Bu varsayımsal değil: bir milyon düğümlük bir zincir çizge, saf özyinelemeli DFS'i pratikte gerçekten çökertebilir.
Konuşma notu: Yönsüz bir çizgede, doğrudan ebeveyninize giden kenar gerçek bir geri kenar değildir -- az önce geldiğiniz aynı kenardır.
Konuşma notu: "Gri"nin tam olarak ne anlama geldiğini ve gri bir düğümün şu anda nerede olduğunu hatırlayın.
Konuşma notu: Bölüm 2'nin animasyonunda graph-terminology.js'nin döngüyü tam olarak bu şekilde bulduğunu hatırlayın.
Konuşma notu: Bölüm 5'in özyineleme riski bu bölümü doğrudan motive ediyor: aynı algoritma, aynı ziyaret sırası, ama çağrı yığını yerine kendi dizi tabanlı yığınımızla.
Konuşma notu: Evet -- ve teknik, bu dersin daha önce bir kez kullandığı bir teknik: Hafta 4'ün yinelemeli orta sıra dolaşması.
Konuşma notu: Bu, Hafta 4'ün yinelemeli orta sıra dolaşmasıyla tam olarak aynı motivasyon, şimdi bir ağaç yerine bir çizgeye uygulanıyor.
Konuşma notu: Bu tek hile, "açık bir yığın" ile "özyinelemeyle tam eşleşen açık bir yığın" arasındaki tüm farktır.
Konuşma notu: Bölüm 5'le aynı normal örnek: 7 düğüm, yönsüz, 4 geri kenar, 10 kenar -- ziyaret sırası birebir aynı çıkıyor.
Konuşma notu: 10 düğüm, 2 ayrı bileşen -- ziyaret edilmemiş her düğümden yeni bir yığın başlar, bileşen başına bir ağaç üretir, tam olarak Bölüm 5'teki gibi.
Konuşma notu: Mümkün olan en yalın dizi tabanlı yığın -- eklemede bir artırma, çıkarmada bir azaltma, başka hiçbir şey yok.
Konuşma notu: "if (visited[u]) continue" satırı önemli: bir düğüm birden fazla kez eklenebilir, ve yalnızca İLK çıkarma sayılmalı.
Konuşma notu: Asıl amaç hiçbir zaman hız değildi -- özyinelemeli sürümün derin çizgelerde riske attığı bir çağrı yığını taşmasından kaçınmaktı.
Konuşma notu: Aynı sıra, aynı karmaşıklık, aynı çıktı -- bu tablo gerçekte hangi yığının kayıt tuttuğuyla ilgili.
Konuşma notu: Eskimiş-kayıt kontrolünü atlamak, özyinelemeyi elle açık bir yığına çevirirken en yaygın hatadır.
Konuşma notu: Bir önceki kod slaytındaki eskimiş-kayıt kontrolünün tam olarak neyi önlemek için orada olduğunu hatırlayın.
Konuşma notu: Bu atma, kodun `if (visited[u]) continue` satırının ele aldığı tam olarak "eskimiş kayıt" durumudur.
Konuşma notu: Bölüm 7, BFS'in kendisini değiştirmeden bir alt yordam olarak yeniden kullanıyor -- tek yeni fikir, onu ziyaret edilmemiş her düğüm için bir kez çağırmak ve her çalıştırmaya kendi etiketini vermek.
Konuşma notu: Bölüm 1 zaten bir çizgenin bağlı olmak zorunda olmadığını söylemişti; bu bölüm "tam olarak ne kadar bağlı değil?" sorusunu yanıtlıyor.
Konuşma notu: "Zayıf" bağlılık, yalnızca bu tek soru için, her yönlü kenarı yönsüzmüş gibi ele almak demektir.
Konuşma notu: Normal örnek: 10 düğüm, yönsüz, 2 bileşen (iki ayrı 5-döngüsü), 10 kenar -- her BFS'in kendi çemberini almasını izleyin.
Konuşma notu: 12 düğüm, yönsüz, 4 ayrı üçgen bileşen, 12 kenar -- bu bölümün animasyonunun aynı anda gösterdiği en fazla bileşen sayısı.
Konuşma notu: Bu, Bölüm 4'ün yalın BFS'i, hiç değişmeden -- yalnız "ziyaret edildi" artık "comp_of == -1" oldu ve bırakılan iz true/false değil bir kimlik.
Konuşma notu: next_id hem bileşenleri sayar HEM de her yeni bileşenin etiketi olur -- tek bir değişken, iki görev.
Konuşma notu: BFS'i birkaç kez, bileşen başına bir kez çalıştırmak, yine de bütün çizge üzerinde tek bir BFS ile aynı O(V + E) toplamına ulaşır.
Konuşma notu: Flood fill özellikle anılmaya değer -- bir çizge düğümü yerine bir piksel ızgarası üzerinde çalışan tam olarak bu algoritmadır.
Konuşma notu: Güçlü bağlılık (yönü dikkate alan), yalın BFS'den fazlasını gerektiren, gerçekten daha zor bir problem -- bu haftanın kapsamı dışında.
Konuşma notu: Birkaç slayt önce "yön göz ardı edilir"in tam olarak ne anlama geldiğini hatırlayın.
Konuşma notu: Güçlü bağlılık hem A>B'yi HEM de B'den A'ya geri bir yolu gerektirirdi -- daha katı, tamamen farklı bir soru.
Konuşma notu: Bölüm 4 zaten her düğümün seviyesini hesaplamıştı; bu bölüm yalnızca uzunluğu değil gerçek en kısa yolu yeniden kurarak bu gerçeği tam olarak açık hale getiriyor.
Konuşma notu: Evet -- ve mekanizma zaten BFS'in çıktısının içinde oturuyor: her düğüme ilk ulaşıldığı anda kaydedilen ebeveyn işaretçisi.
Konuşma notu: Burada yeni bir mekanizma yok -- Bölüm 4'ün BFS'i, artı zaten kurduğu ebeveyn işaretçilerinde geriye doğru kısa bir yürüyüş.
Konuşma notu: Normal örnek: 7 düğüm, yönsüz, s=A, t=F, 10 kenar -- BFS sırasında ebeveyn[]'in dolmasını, sonunda geriye izlenmesini gözlemleyin.
Konuşma notu: 9 düğüm, s=A, t=H, 2 ayrı bileşende -- kuyruk boşalır ve t hiç ziyaret edilmez, o yüzden hiçbir yol bildirilemez.
Konuşma notu: Bölüm 4'ün BFS döngüsüyle birebir aynı, tek farkla: bu sürümün TEK amacı parent_of'u doğru doldurmak.
Konuşma notu: Yürüyüş yolu geriye, t'den s'ye doğru kurar, çünkü ebeveyn işaretçilerinin gittiği tek yön budur -- sonunda tersine çevirmek sırayı düzeltir.
Konuşma notu: Gerçek yolu yeniden kurmak, zaten çoğu zaman çalıştırıyor olacağınız bir BFS'in üstüne neredeyse bedavaya geliyor.
Konuşma notu: Yalnızca UZUNLUK garantili biçimde tekildir -- tam düğüm dizisi, alfabetik sıra gibi eşit-kırma seçimlerine bağlıdır.
Konuşma notu: BFS'in yalın kuyruğu her zaman kenar sayısına göre en yakın ZİYARET EDİLMEMİŞ düğümü genişletir; Dijkstra bunun yerine bir öncelik kuyruğu koyar ve gerçek mesafeye göre genişletir.
Konuşma notu: Bu üç hatanın her biri çökmeden çalışmaya devam eder -- hata yalnızca yazdırılan yolun kendisinde ortaya çıkar.
Konuşma notu: Geriye izleme kodunun yaptığı ilk kontrolü, birkaç slayt önce, hatırlayın.
Konuşma notu: Bu, yukarıdaki "yol yok" uç durum animasyonunun göstermek için kurulduğu durumun ta kendisi.
Konuşma notu: İki gösterim, bir takas tablosu -- sonraki her algoritmanın karmaşıklığı bu satıra dayanıyor.
Konuşma notu: Bu dört satırın her biri aynı iki hareketten kuruludur: ekle/çıkar (kuyruk), ya da it/çek (yığın).
Konuşma notu: Bir öğrenci bugünden yalnızca bir cümle hatırlayacaksa, hatırlamaya değer olan bu.
Konuşma notu: Bunlar, yazılı notların sonundaki öz-değerlendirme sınavını yansıtıyor, burada slayt başına bir soru, daha kısa bir seçkiyle.
Konuşma notu: Sor, bekle, sonra devam et.
Konuşma notu: n düğümlü, yönsüz bir tam çizgenin her zaman n(n-1)/2 kenarı vardır.
Konuşma notu: Bölüm 4'ün gölete atılan taş sezgisini hatırlayın.
Konuşma notu: Yalnızca veri yapısını değiştirmek, bu iki dolaşma sırası arasındaki tüm farktır.
Konuşma notu: Bölüm 5'in kenar türü tablosunu hatırlayın.
Konuşma notu: Bu, graph-terminology.js'in Bölüm 2'de döngüyü bulmak için kullandığı tam olarak aynı teknik.
Konuşma notu: Birkaç slayt önce Bölüm 7'nin terimini hatırlayın.
Konuşma notu: Bu ayrımı tam olarak hatırlamaya değer, çünkü ikisi aynı çizgede gerçekten farklı yanıtlar verir.
Konuşma notu: Karma tablolar (hashing), bu haftanın "her şeyi keşfet" fikrini tamamen farklı bir fikirle takas ediyor: nereye bakacağını tek adımda tam olarak hesapla.
Konuşma notu: Bunlar, haftanın yazılı notlarının sonunda listelenen aynı kaynaklar.
Konuşma notu: Tarihsel kaynaklar -- Euler, Moore, Hopcroft ve Tarjan -- bugünkü "kısa tarihçe" slaytlarının dayandığı kaynaklardı.