Latihan 1: BFS & DFS (Graph Traversal) — Algoritma

Latihan 1 dari materi BFS & DFS (Graph Traversal) di Algoritma — praktek dengan editor kode interaktif, test case otomatis, dan hint terpandu. Langsung jalan di browser.

Lengkapi bfsDistance(adj, start) supaya mengembalikan object berisi jarak terpendek (jumlah jalan paling sedikit) dari start ke tiap node yang bisa dicapai.

adj adalah adjacency list berupa object: adj[node] adalah array tetangga node itu.
start adalah node awal, dan jaraknya ke dirinya sendiri 0.
Pakai BFS dengan queue: tetangga yang belum punya jarak dapat jarak node sekarang tambah 1.
Node yang gak bisa dicapai dari start jangan dimasukkan ke hasil sama sekali (jangan diisi Infinity atau -1).

Kode di bawah function jangan diubah. Untuk graph di starter, output-nya harus empat baris ini, berurutan:

0 (jarak A)
1 (jarak B)
2 (jarak D)
2 (jarak E)

Function-nya juga dicek dengan graph lain.

Hint

BFS mengunjungi node lapis demi lapis, jadi jarak pertama yang dicatat untuk sebuah node sudah yang terpendek. Simpan jaraknya di object, dan pakai object itu juga sebagai tanda sudah ketemu.
Mulai dengan dist[start] = 0 dan queue berisi start. Selama queue gak kosong, ambil node dari depan pakai shift. Untuk tiap tetangga yang dist-nya masih undefined, isi dist[node] + 1 lalu push ke queue.
const dist = {}; dist[start] = 0; const queue = [start]; while (queue.length > 0) { const node = queue.shift(); for (const next of adj[node]) { if (dist[next] === undefined) { dist[next] = dist[node] + 1; queue.push(next); } } } return dist;

</> { } .css => #id fn()

Versi baru

HyperSheets

bagian dari BelajarWeb.dev

Membuka gerbang…

Latihan 1: BFS & DFS (Graph Traversal) — Algoritma

Hint

Memperbarui Aplikasi