Implementasi (Bagian 2)
Pelajaran 6 dari 9 dalam kursus Breadth-First Search: Algoritma Graf di Coddy.
Sekarang kita menelusuri graf per lapisan menggunakan antrean.
Tantangan
SedangSekarang, buat penelusuran lengkapnya.
Tulis fungsi bernama bfs yang menerima n, array edges datar (tak berarah), dan simpul start, lalu mengembalikan urutan simpul yang dikunjungi BFS dari start.
Buat adjacency list (tetangga diurutkan menaik), lalu gunakan queue: tandai dan masukkan simpul awal ke queue, lalu berulang kali keluarkan simpul dari queue, catat simpul tersebut, dan masukkan tetangganya yang belum dikunjungi ke queue. Hanya simpul yang dapat dijangkau dari start yang dikunjungi.
Coba sendiri
#include <stdlib.h>
int* bfs(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 Breadth-First Search: Algoritma Graf
2Algoritma
Cara kerjanya?Kode SemuImplementasi (Bagian 1)Implementasi (Bagian 2)
Kompleksitas Waktu dan RuangLatihan sendiri: Compiler C online