Özet - Topological sort
- Algoritmalar kursu
- İleri seviye
- Ders 48/56
- 4 dk
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.
Başlangıç kodu
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Ö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
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()))Beklenen çıktı
[0, 1, 2, 3]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 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 Doğru cevap
Açıklama: Döngü varsa topolojik sıralama mümkün değildir.
2 sıraya ekleme
Soru
order.____(u)
Cevap
order.append(u)Açıklama: append doğru.
3 Özet - Topological sort: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
init_graph |
Graf |
compute_indegree |
Derece |
kahn_sort |
Sıralama |
queue |
Kuyruk |