DFS tabanlı sıralama
- Algoritmalar kursu
- İleri seviye
- Ders 46/56
- 4 dk
DFS bitiş sırasının tersini alarak topolojik sıra bulmayı öğrenirsin.
Giriş derecesi
Bir düğümün giriş derecesi (in-degree), kendisine gelen kenar sayısıdır. Giriş derecesi sıfır olan düğümler sıralamada ilk gelir.
Kahn algoritması, giriş derecesi sıfır olan düğümleri bir kuyruğa ekleyip tek tek çıkararak sıralamayı bulur.
Derece dizisi
Tüm düğümlerin giriş dereceleri tek bir dizide toplanır. Bu dizi, Kahn algoritmasının başlangıç durumunu belirler.
Derece dizisi, bağımlılık ilişkilerinin özetidir. Sıfır olan düğümler bağımsızdır ve önce işlenir.
Uygulama compute_indegree fonksiyonu
compute_indegree(graph) yaz. Her düğümün giriş derecesini hesapla, dizi döndür. print(compute_indegree(init_graph())) ile yazdır.
Başlangıç kodu
def init_graph():
# Komşuluk listesini döndür
return [[1, 2], [3], [3], []]
def compute_indegree(graph):
# Giriş derecelerini hesaplaÖrnek çözüm
def init_graph():
# Komşuluk listesini döndür
return [[1, 2], [3], [3], []]
def compute_indegree(graph):
# Giriş derecelerini hesapla
n = len(graph)
indegree = [0] * n
for u in range(n):
for v in graph[u]:
indegree[v] += 1
return indegree
print(compute_indegree(init_graph()))Beklenen çıktı
[0, 1, 1, 2]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 giriş derecesi
indegree[____] += 1indegree[v] += 1Açıklama: v doğru.
2 Düğüm 3'ün giriş derecesi nedir?
- 0
- 2 Doğru cevap
- 1
- 3
Açıklama: 1 ve 2'den kenar gelir, yani giriş derecesi 2'dir.
3 DFS tabanlı sıralama: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
0 |
bağımsız |
1 |
0→1 |
2 |
0→2 |
3 |
1,2→3 |