BFS
Pelajaran 10 dari 14 dalam kursus Graf, Seri Struktur Data #9 di Coddy.
Tantangan berikutnya dirancang untuk menggunakan class Graph yang baru saja kamu buat.
Setiap tantangan menyediakan file graph terkunci (Graph terakhir dari bab sebelumnya) dan file solution baru tempat kamu menulis fungsi yang menggunakan Graph.
Algoritma pertama kita: Pencarian Melebar (Breadth-First Search). Dimulai dari sebuah simpul, BFS mengunjungi semua simpul yang dapat dijangkau secara bertahap: pertama simpul awal, lalu semua simpul yang berjarak satu sisi, kemudian semua simpul yang berjarak dua sisi, dan seterusnya. Implementasi klasik menggunakan antrean: masukkan simpul awal ke antrean, lalu berulang kali keluarkan simpul dari antrean, catat simpul itu sebagai sudah dikunjungi, dan masukkan tetangga yang belum dikunjungi ke antrean.
Karena daftar tetangga tidak memiliki urutan tetap, dua proses BFS yang benar dapat menghasilkan urutan penelusuran yang berbeda. Agar jawaban dalam tantangan ini deterministik, urutkan tetangga setiap simpul secara menaik sebelum memasukkannya ke antrean.
Tantangan
MudahTulis fungsi bfs yang menerima array int 2D adjacency (setiap baris berupa sisi [u, v]) dan int start, lalu mengembalikan urutan kunjungan BFS dari start sebagai list int.
Buat graf: untuk setiap [u, v] dalam adjacency, panggil g.addEdge(u, v). Lalu jalankan BFS dari start menggunakan antrean. Saat memproses tetangga sebuah vertex, urutkan secara menaik agar output tetap konsisten.
Kamu harus menggunakan class Graph (disediakan dalam graph), jangan gunakan bawaan bahasa (maps, sets) untuk memodelkan adjacency. Data tambahan untuk algoritma (set visited, antrean) boleh menggunakan tipe dari stdlib.
Coba sendiri
#include <stdio.h>
#include "solution.h"
int main() {
int n, m, start;
if (scanf("%d %d %d", &n, &m, &start) != 3) return 0;
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
int out[MAX_VERTICES];
int outn = bfs(adjacency, m, start, out);
for (int i = 0; i < outn; i++) {
if (i > 0) printf(" ");
printf("%d", out[i]);
}
printf("\n");
return 0;
}
Semua pelajaran di Graf, Seri Struktur Data #9
Latihan sendiri: Compiler C online