Implementasi (Bagian 2)
Pelajaran 6 dari 9 dalam kursus Depth-First Search: Algoritma Graf di Coddy.
Sekarang kita menelusuri seluruh graf dengan stack.
Tantangan
SedangSekarang, buat penelusuran lengkap.
Tulis fungsi bernama dfs yang menerima n, array edges datar (tak berarah), dan simpul start, lalu mengembalikan urutan simpul yang dikunjungi DFS, dimulai dari start.
Pertama, buat adjacency list (urutkan tetangga setiap simpul secara menaik). Lalu jalankan DFS iteratif dengan stack. Hanya simpul yang dapat dijangkau dari start yang dikunjungi.
Untuk mengunjungi tetangga dalam urutan menaik, masukkan mereka ke stack dari yang terbesar hingga terkecil.
Coba sendiri
#include <stdlib.h>
int* dfs(int n, int* edges, int edges_size, int start, 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 Depth-First Search: Algoritma Graf
2Algoritma
Cara kerjanya?Kode semuImplementasi (Bagian 1)Implementasi (Bagian 2)
Kompleksitas waktu dan ruangLatihan sendiri: Compiler C online