Veri Yapıları #10 | Çizgeler: Komşuluk Listesi, Genişlik ve Derinlik Öncelikli Arama

Eğitmen: Dr. Süleyman Burak ÇELİK

Veri Yapıları dersinin onuncu ve son videosu. Bir çizgede A'dan H'ye en az kaç kenarla gidilir? Genişlik öncelikli arama 4 kenarlık bir yol buluyor, derinlik öncelikli arama ise 6 kenarlık bir yoldan varıyor. İkisinin neden farklı davrandığını görüyoruz. Çizgede ağaçtaki ebeveyn kısıtı yoktur: düğümler ve onları ikişer ikişer bağlayan kenarlar vardır. Yönlü ve yönsüz çizgeyi, yolu, yolun uzunluğunu, döngüyü ve bağlılığı 8 düğümlü, 10 kenarlı bir örnek çizgede tanımlıyoruz. Çizgeyi bellekte iki yolla tutuyoruz: komşuluk matrisi (8 × 8 = 64 hücre; yönsüz çizgede her kenar iki hücrede, 20 tane 1) ve komşuluk listesi (8 baş, 20 kayıt). Seyrek bir sokak ızgarasında farkı ölçüyoruz: 3000 kavşak ve 5890 sokak için matris 9 milyon hücre isterken listelerde 3000 baş ve 11 780 kayıt yetiyor. Genişlik öncelikli aramayı 7. dersteki kuyrukla yazıp çizgenin katman katman açılışını izliyoruz; her düğümün önceki işaretçisini geriye izleyerek A'dan H'ye en az kenarlı yolu buluyoruz. Derinlik öncelikli aramayı özyinelemeyle yazıyoruz: programın girintisi çağrı yığınının derinliğini gösteriyor ve H'ye 6 çağrı derinde, en kısa olmayan bir yoldan varılıyor. Son olarak derinlik öncelikli aramayla bileşenleri buluyor ve seriyi kapatıyoruz. Ekrandaki her çıktı, kodun gerçekten derlenip çalıştırılmasından geliyor. Bu derste: 1. Çizge kavramları: düğüm, kenar, yönlü/yönsüz, yol, döngü, bağlılık 2. Komşuluk matrisi ve komşuluk listesi; seyrek çizge 3. Genişlik öncelikli arama: kuyruk, katmanlar, en az kenarlı yol 4. Derinlik öncelikli arama: özyineleme ve çağrı yığını 5. Bileşenler ve aramaların maliyeti (düğüm + kenar) Bölümler: 0:00 Ağaçtan çizgeye 0:23 A'dan H'ye kaç kenar? 0:42 Yol, döngü, bağlılık 1:05 Komşuluk matrisi 1:36 Komşuluk listesi ve seyrek çizge 2:15 Genişlik öncelikli arama 2:55 En kısa yol: öncekileri izle 3:28 Derinlik öncelikli arama 4:09 Bileşenler 4:35 Bugünün dört kuralı 4:57 Seri tamamlandı Kaynak kitap: Mark Allen Weiss — Data Structures and Algorithm Analysis in C++, 4. baskı (2014), §9.1 (tanımlar, komşuluk matrisi ve komşuluk listesi), §9.3.1 (ağırlıksız en kısa yollar: kuyrukla genişlik öncelikli arama) ve §9.6 (derinlik öncelikli arama ve bağlılık). Konu sırası ve kavramlar kaynak kitaptan izlenir; programlar ve örnekler C ile özgün yazıldı, anlatım ve ekranlar özgündür. Hedef kitle: veri yapılarına başlayan mühendislik ve bilgisayar/yazılım öğrencileri. Ön koşul: temel C, özyineleme ve bu serinin 3., 6. ve 7. dersleri (bağlı liste, yığın, kuyruk).

Bu videoyu izlemek için Premium üyelik gerekir.