Implementasi (Bagian 1)
Pelajaran 5 dari 9 dalam kursus Depth-First Search: Algoritma Graf di Coddy.
Kita akan membangun DFS mulai dari pencarian adjacency.
Tantangan
MudahSebelum menelusuri graph, kita perlu mengetahui tetangga setiap vertex. Mari buat pencarian tersebut dari daftar edge yang datar.
Tulis fungsi bernama getNeighbors yang menerima array edges (pasangan datar [u0, v0, u1, v1, ...], tidak berarah) dan sebuah vertex node, lalu mengembalikan daftar terurut tetangga node, tanpa duplikat.
Contohnya, getNeighbors([0,1, 0,2, 1,2, 3,0], 0) mengembalikan [1, 2, 3].
Coba sendiri
#include <stdlib.h>
int* getNeighbors(int* edges, int edges_size, int node, 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