Implementation (Part 2)
Coddy'nin Topolojik Sıralama - Graf Algoritmaları kursunda ders 6 / 9.
Şimdi, sıralamayı oluşturmak için giriş derecesi 0 olan köşeleri tekrar tekrar kaldırıyoruz.
Görev
OrtaŞimdi tam sıralamayı oluşturun.
n ve düz edges dizisini (yönlendirilmiş u -> v) alan ve köşelerin topolojik sıralamasını döndüren topologicalSort adında bir fonksiyon yazın.
Kahn algoritmasını kullanın: giriş derecelerini (in-degrees) hesaplayın, ardından giriş derecesi 0 olan en küçük köşeyi tekrar tekrar alın, onu ekleyin ve dış komşularının giriş derecesini azaltın. Bu görev için girdiler döngüsüzdür (acyclic).
Her adımda mevcut olan en küçük köşeyi almak, cevabı benzersiz kılar.
Kendin dene
#include <stdlib.h>
int* topologicalSort(int n, int* edges, int edges_size, int* returnSize) {
// Kodu buraya yazın
*returnSize = 0;
return edges;
}
Kendini test etBu ders kısa bir quiz içerir. Soruları yanıtlamak ve ilerlemeni kaydetmek için derse başla.
Topolojik Sıralama - Graf Algoritmaları bölümündeki tüm dersler
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity