Özet - Topological sort

Topolojik sırayı yazdıran mini görev yaparsın.

Özet - Topological sort

Bu grupta bağımlılık sırasını bulan topolojik sıralamayı öğrendin. Komşuluk listesi, giriş derecesi ve Kahn algoritması birleşince çözüm oluşur.

Şimdi tüm parçaları bir araya getiren bir fonksiyon yazacaksın. Bu özet, grubun kavramlarını tek bir kodda birleştirir.

Uygulama topological_order fonksiyonu

topological_order(graph) yaz. compute_indegree hazır; Kahn ile sırala. print(topological_order(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 topological_order(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(topological_order(init_graph()))

Kendini test et

Topolojik sıralama ne zaman mümkün değildir?
- Graf boşsa
- Graf tek düğümlüye
- Graf yönsüzse
- Grafta döngü varsa
Cevabı göster

Grafta döngü varsa — Döngü varsa topolojik sıralama mümkün değildir.
sıraya ekleme
```
order.____(u)
```
Cevabı göster
```
order.append(u)
```
Özet - Topological sort: kavramları eşleştir

init_graph

Graf
compute_indegree

Derece
kahn_sort

Sıralama
queue

Kuyruk

Sıradaki ders: Union-find

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler