Implementasi (Bagian 2)
Pelajaran 6 dari 9 dalam kursus Pengurutan Topologis, Algoritma Graf di Coddy.
Sekarang kita berulang kali menghapus simpul dengan derajat masuk 0 untuk menyusun urutannya.
Tantangan
SedangSekarang susun urutan lengkapnya.
Tulis fungsi bernama topologicalSort yang menerima n dan array edges datar (berarah u -> v), lalu mengembalikan urutan topologis simpul-simpulnya.
Gunakan algoritma Kahn: hitung derajat masuk, lalu berulang kali ambil simpul terkecil yang berderajat masuk 0, tambahkan ke urutan, dan kurangi derajat masuk tetangga keluarannya. Input untuk tantangan ini tidak memiliki siklus.
Mengambil simpul terkecil yang tersedia pada setiap langkah membuat jawabannya unik.
Coba sendiri
#include <stdlib.h>
int* topologicalSort(int n, int* edges, int edges_size, int* returnSize) {
// Tulis kodemu di sini
*returnSize = 0;
return edges;
}
Uji dirimuPelajaran ini berisi kuis singkat. Mulai pelajarannya untuk menjawab kuis dan melacak progresmu.
Semua pelajaran di Pengurutan Topologis, Algoritma Graf
2Algoritma
Cara kerjanya?Kode SemuImplementasi (Bagian 1)Implementasi (Bagian 2)
Kompleksitas Waktu dan RuangLatihan sendiri: Compiler C online