Bağımlılık sırası

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.

Örnek çözümü göster

def init_graph():
    # Komşuluk listesini döndür
    return [[1, 2], [3], [3], []]
print(init_graph())

Kendini test et

Topolojik sıralama hangi grafta mümkündür?
- Yönlü döngüsüz (DAG)
- Yönsüz
- Yönlü döngülü
- Tam bağlı
Cevabı göster

Yönlü döngüsüz (DAG) — Topolojik sıralama DAG'da mümkündür.
kenar tanımı
```
graph[0] = [____, 2]
```
Cevabı göster
```
graph[0] = [1, 2]
```
Bağımlılık sırası: kavramları eşleştir

graph[0]

0'dan 1,2'ye
graph[1]

1'den 3'e
graph[2]

2'den 3'e
graph[3]

çıkış yok

Sıradaki ders: DFS tabanlı sıralama

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler