Pencarian graf: BFS dan DFS

Pada 1736 Leonhard Euler menunjukkan bahwa tidak ada rute jalan kaki yang melintasi ketujuh jembatan Königsberg masing-masing tepat sekali, dan teori graf berawal dari jawaban itu.

Titik dan garis

Graf adalah himpunan titik, yang disebut simpul (vertex atau node), yang dihubungkan oleh garis, yang disebut sisi (edge). Gagasannya sederhana, tetapi cocok untuk banyak sekali hal: kota yang dihubungkan jalan, halaman web yang dihubungkan tautan, orang yang dihubungkan pertemanan, petak labirin yang terhubung di tempat yang tidak berdinding. Begitu sebuah masalah digambar sebagai graf, segelintir algoritma yang sama bisa menjawab pertanyaan seperti "bisakah aku pergi dari sini ke sana?" dan "jalan mana yang terpendek?"

Menyimpan graf dalam kode

Cara yang umum untuk menyimpan graf adalah daftar ketetanggaan (adjacency list): untuk setiap simpul, daftar tetangganya. Catatan kuliah 6.006 MIT memakai cara ini, yaitu array atau kamus Adj dengan Adj[u] berisi simpul-simpul yang terhubung ke u. Untuk graf di atas bentuknya seperti ini:

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "D", "E"],
  D: ["B", "C", "F"],
  E: ["C", "F"],
  F: ["D", "E"],
};

Pencarian melebar (breadth-first search): lapis demi lapis

Pencarian melebar (BFS) menjelajahi graf berlapis-lapis di sekitar titik awal. Pertama titik awal itu sendiri, pada jarak 0. Lalu semua tetangganya, pada jarak 1. Lalu setiap simpul baru di sebelah simpul-simpul itu, pada jarak 2, dan seterusnya. Untuk itu BFS menyimpan antrean (queue), yaitu barisan tempat yang pertama masuk menjadi yang pertama keluar. Ambil simpul di depan antrean, kunjungi, lalu tambahkan tetangganya yang belum terlihat ke belakang antrean. Dari A pada contoh, BFS mengunjungi A, lalu B dan C, lalu D dan E, lalu F. Karena bergerak keluar satu lapis demi satu lapis, saat pertama kali BFS mencapai sebuah simpul, ia sudah menemukan jalur dengan sisi paling sedikit. F berjarak 3 sisi dari A, misalnya A, B, D, F.

function bfs(graph, start) {
  const seen = new Set([start]);
  const queue = [start];
  const order = [];
  while (queue.length) {
    const u = queue.shift();        // masuk pertama, keluar pertama
    order.push(u);
    for (const v of graph[u]) {
      if (!seen.has(v)) { seen.add(v); queue.push(v); }
    }
  }
  return order;   // A B C D E F
}

Pencarian mendalam (depth-first search): sejauh mungkin, lalu mundur

Pencarian mendalam (DFS) berperilaku seperti orang di labirin yang menjaga satu tangannya tetap menempel di dinding. DFS mengikuti satu jalur sedalam mungkin. Ketika sampai di jalan buntu atau tempat yang sudah pernah dilihat, ia mundur ke titik pilihan terakhir dan mencoba pilihan berikutnya. DFS memakai tumpukan (stack), bukan antrean, masuk terakhir keluar pertama, dan sangat wajar ditulis dengan rekursi, karena tumpukan pemanggilanlah yang mengingat. Dari A, DFS rekursif mengunjungi A, B, D, C, E, F. DFS mencapai setiap simpul yang dicapai BFS, tetapi jalur yang diikutinya belum tentu yang terpendek.

function dfs(graph, u, seen = new Set(), order = []) {
  seen.add(u);
  order.push(u);
  for (const v of graph[u]) if (!seen.has(v)) dfs(graph, v, seen, order);
  return order;   // A B D C E F
}

Mana yang dipakai

Pada labirin pertama di laboratorium, BFS mengunjungi 105 petak dan menemukan jalur 22 gerakan, yang terpendek. DFS kebetulan menukik ke arah tujuan dan hanya mengunjungi 31 petak, tetapi jalurnya butuh 28 gerakan. Tidak ada yang selalu lebih murah. Keduanya menangani setiap simpul dan setiap sisi dalam jumlah kali yang tetap, jadi keduanya berjalan dalam waktu O(V + E) untuk V simpul dan E sisi. Pilih BFS kalau kamu butuh langkah paling sedikit: gerakan paling sedikit dalam teka-teki, tautan paling sedikit antara dua orang. Pilih DFS kalau kamu perlu menjelajahi semuanya atau mengikuti pilihan sampai ujung: memeriksa apakah setiap ruangan labirin terhubung, atau mencoba gerakan teka-teki satu jalur demi satu jalur dan mundur saat buntu. Kalau sisi-sisinya punya panjang berbeda, seperti jalan raya, keduanya saja tidak cukup; metode seperti algoritma Dijkstra memperluas gagasan BFS dengan jarak.