Motivation
Coddy'nin Topolojik Sıralama - Graf Algoritmaları kursunda ders 2 / 9.
Topolojik sıralama yalnızca grafikte döngü olmadığında mevcuttur. Gelen kenarı kalmamış bir düğümü tekrar tekrar kaldıran Kahn algoritması ile bir tane oluştururuz.
Neden Topolojik Sıralama öğrenilmeli?
- Kısıtlamalarla sıralama: derleme sistemleri, görev planlama, ders önkoşulları ve hesap çizelgesi yeniden hesaplamalarının tümü buna dayanır.
- Döngü tespiti: eğer her düğümü sıralayamazsanız, grafik bir döngü içermelidir.
- DAG algoritmaları için temel: bir DAG'daki en kısa ve en uzun yollar topolojik sırada hesaplanır.
Birçok geçerli sıralama mevcut olabilir. Tahmin edilebilir tek bir yanıt almak için, her zaman giriş derecesi 0 olan en küçük numaralı düğümü kaldırırız.
Kendin dene
Bu ders bir kod alıştırması içermiyor.
Kendini test etBu ders kısa bir quiz içerir. Soruları yanıtlamak ve ilerlemeni kaydetmek için derse başla.
