Kahn algoritması

Derece sayımı ile sıralama yapmayı öğrenirsin.

Kahn algoritması

Kahn algoritması, giriş derecesi sıfır olan düğümleri bir kuyruğa ekler. Kuyruktan bir düğüm çıkarılır, sıraya eklenir ve komşularının dereceleri azaltılır.

Derecesi sıfıra düşen komşular kuyruğa eklenir. Kuyruk boşalınca sıralama tamamlanır.

Sıralama tamamlanma

Kuyruk boşaldığında sıralama dizisi tüm düğümleri içeriyorsa işlem başarılıdır. Eğer sıra n'den azsa grafta döngü vardır ve topolojik sıralama mümkün değildir.

Kahn algoritması bu şekilde hem sıralar hem döngü denetler. Çıktı, düğümlerin bağımlılık sırasıdır.

Uygulama kahn_sort fonksiyonu

kahn_sort(graph) yaz. compute_indegree hazır; sıfır derecelileri kuyruğa al, sırala. print(kahn_sort(init_graph())) ile [0, 1, 2, 3] 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
def kahn_sort(graph):
    # Topolojik sırayı bul
    n = len(graph)
    indegree = compute_indegree(graph)
    queue = [i for i in range(n) if indegree[i] == 0]
    order = []
    while queue:
        u = queue.pop(0)
        order.append(u)
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
    return order
print(kahn_sort(init_graph()))

Kendini test et

Kahn algoritması: kavramları eşleştir

kuyruk

Sıfır derece
sıra

Sonuç
indegree

Derece
komşu

Azalt
Örnek DAG için topolojik sıra nedir?
- [1, 0, 3, 2]
- [3, 2, 1, 0]
- [0, 1, 2, 3]
- [0, 3, 1, 2]
Cevabı göster

[0, 1, 2, 3] — 0 bağımsız, diğerleri sırayla gelir.
kuyruk işlemi
```
u = queue.pop(____)
```
Cevabı göster
```
u = queue.pop(0)
```

Sıradaki ders: Özet - Topological sort

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler