Bağımlılık sırası
- Algoritmalar kursu
- İleri seviye
- Ders 45/56
- 4 dk
Yönlü çevresiz graph'ta bağımlılık sırası bulmayı öğrenirsin.
Bağımlılık sırası
Topolojik sıralama, bir yönlü döngüsüz grafta (DAG) düğümleri bağımlılık sırasına göre dizer. Her düğüm, kendisine bağımlı tüm düğümlerden sonra gelir.
Derleme görevleri, ders ön koşulları gibi bağımlılıkların olduğu her yerde kullanılır. Döngü varsa sıralama mümkün değildir.
Komşuluk listesi
Graf, her düğümün sonraki düğümlerini içeren komşuluk listesiyle temsil edilir. Örneğin graph[0] = [1, 2], 0'dan 1 ve 2'ye kenar olduğunu gösterir.
Bu gösterim, bağımlılık ilişkilerini net biçimde ifade eder. Her düğüm yalnızca kendisine bağımlı düğümleri listeler.
Uygulama init_graph fonksiyonu
init_graph() yaz. Komşuluk listesini döndür. print(init_graph()) ile yazdır.
Başlangıç kodu
def init_graph():
# Komşuluk listesini döndürÖrnek çözüm
def init_graph():
# Komşuluk listesini döndür
return [[1, 2], [3], [3], []]
print(init_graph())Beklenen çıktı
[[1, 2], [3], [3], []]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Topolojik sıralama hangi grafta mümkündür?
- Yönlü döngüsüz (DAG) Doğru cevap
- Yönsüz
- Yönlü döngülü
- Tam bağlı
Açıklama: Topolojik sıralama DAG'da mümkündür.
2 kenar tanımı
graph[0] = [____, 2]graph[0] = [1, 2]Açıklama: 1 doğru.
3 Bağımlılık sırası: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
graph[0] |
0'dan 1,2'ye |
graph[1] |
1'den 3'e |
graph[2] |
2'den 3'e |
graph[3] |
çıkış yok |