DFS tabanlı sıralama

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.

Örnek çözümü göster

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()))

Kendini test et

giriş derecesi
```
indegree[____] += 1
```
Cevabı göster
```
indegree[v] += 1
```
Düğüm 3'ün giriş derecesi nedir?
- 0
- 2
- 1
- 3
Cevabı göster

2 — 1 ve 2'den kenar gelir, yani giriş derecesi 2'dir.
DFS tabanlı sıralama: kavramları eşleştir

0

bağımsız
1

0→1
2

0→2
3

1,2→3

Sıradaki ders: Kahn algoritması

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler