Bagian 3: Implementasi BFS dan DFS

Fondasi sudah siap: kita punya struct State, fungsi getNeighbors, dan hasher untuk unordered_set. Sekarang waktunya menjalankan algoritma pencarian. BFS dengan std::queue menjamin solusi optimal (jumlah gerakan minimum) karena setiap edge berbobot 1. DFS dengan std::stack lebih ringan secara memori tetapi tidak menjamin optimal — penting untuk pemahaman trade-off. Pada bagian ini kita menulis kedua algoritma, lengkap dengan rekonstruksi jalur menggunakan parent map, lalu membandingkan hasilnya pada state awal yang sama.

Aturan: BFS = Optimal pada Bobot Seragam #

Pada graph di mana setiap edge berbobot sama (di sini semua gerakan berbobot 1), BFS menjamin jalur terpendek. Alasannya sederhana: BFS mengunjungi state level demi level. State pada level k terjangkau dalam k gerakan — dan tidak ada gerakan yang lebih sedikit.

flowchart LR S[start] --> A1[nb 1] S --> A2[nb 2] A1 --> B1[nb 1.1] A1 --> B2[nb 1.2] A2 --> B3[nb 2.1] B1 --> G[goal] style G fill:#9f9

Pada diagram di atas, BFS akan menemukan goal di level 3, melalui jalur start → nb 1 → nb 1.1 → goal. Tidak ada jalur lebih pendek karena level 1 dan 2 sudah diperiksa tanpa menemukan goal.

Mekanisme: Queue, Visited Set, Parent Map #

Tiga struktur data menjadi tulang punggung BFS:

std::queue<State> — antrian FIFO berisi state yang akan diproses.
unordered_set<State, StateHash> — catatan state yang sudah masuk queue (menghindari duplikat).
unordered_map<State, State, StateHash> — parent setiap state, untuk rekonstruksi jalur.

Loop BFS:

text
queue.push(start); visited.insert(start); parent[start] = start
while queue not empty:
  cur = queue.front(); queue.pop()
  if cur == goal: break
  for nb in getNeighbors(cur):
    if nb not in visited:
      visited.insert(nb)
      parent[nb] = cur
      queue.push(nb)

DFS: Stack Pengganti Queue #

DFS mengganti queue dengan stack. Sisanya sama persis: visited set, parent map, loop utama. Perbedaan perilaku: DFS akan mendalami satu cabang sampai buntu sebelum backtrack.

Tanpa batas kedalaman, DFS pada 8-puzzle bisa mengunjungi ribuan state sebelum menemukan solusi. Karena itu kita tambahkan maxDepth — bila kedalaman saat ini sudah mencapai batas, kita tidak menambah tetangga baru ke stack. Batas ini membuat DFS selesai dalam waktu terkontrol.

text
stack.push((start, 0)); visited.insert(start); parent[start] = start
while stack not empty:
  (cur, d) = stack.top(); stack.pop()
  if cur == goal: break
  if d + 1 > maxDepth: continue          // jangan ekspansi lebih dalam
  for nb in getNeighbors(cur):
    if nb not in visited:
      visited.insert(nb); parent[nb] = cur; stack.push((nb, d+1))

Program Lengkap Bagian 3 #

Program berikut mengimplementasikan BFS dan DFS, plus rekonstruksi jalur. Pengujian membandingkan kedua algoritma pada state awal 1 2 3 4 0 6 7 5 8.

cpp
#include <iostream>
#include <array>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <cstdint>
#include <utility>
#include <algorithm>

struct State {
    std::array<int, 9> tiles;
    bool operator==(const State& o) const { return tiles == o.tiles; }
    bool operator!=(const State& o) const { return tiles != o.tiles; }
};

const State GOAL{{{1, 2, 3, 4, 5, 6, 7, 8, 0}}};

int findBlank(const State& s) {
    for (int i = 0; i < 9; ++i) if (s.tiles[i] == 0) return i;
    return -1;
}

static int rowOf(int i) { return i / 3; }
static int colOf(int i) { return i % 3; }

enum class Move { UP, DOWN, LEFT, RIGHT };

bool canMove(int blankIndex, Move m) {
    int r = rowOf(blankIndex), c = colOf(blankIndex);
    switch (m) {
        case Move::UP:    return r > 0;
        case Move::DOWN:  return r < 2;
        case Move::LEFT:  return c > 0;
        case Move::RIGHT: return c < 2;
    }
    return false;
}

int swapTarget(int blankIndex, Move m) {
    int r = rowOf(blankIndex), c = colOf(blankIndex);
    switch (m) {
        case Move::UP:    return (r - 1) * 3 + c;
        case Move::DOWN:  return (r + 1) * 3 + c;
        case Move::LEFT:  return r * 3 + (c - 1);
        case Move::RIGHT: return r * 3 + (c + 1);
    }
    return blankIndex;
}

State applyMove(const State& s, Move m) {
    int b = findBlank(s);
    State next = s;
    if (canMove(b, m)) {
        int target = swapTarget(b, m);
        std::swap(next.tiles[b], next.tiles[target]);
    }
    return next;
}

std::vector<State> getNeighbors(const State& s) {
    std::vector<State> result;
    for (Move m : {Move::UP, Move::DOWN, Move::LEFT, Move::RIGHT}) {
        State next = applyMove(s, m);
        if (next != s) result.push_back(next);
    }
    return result;
}

struct StateHash {
    std::size_t operator()(const State& s) const {
        std::size_t h = 0;
        for (int i = 0; i < 9; ++i) h = h * 31 + s.tiles[i];
        return h;
    }
};

using StateSet = std::unordered_set<State, StateHash>;
using ParentMap = std::unordered_map<State, State, StateHash>;

void print(const State& s) {
    for (int r = 0; r < 3; ++r) {
        for (int c = 0; c < 3; ++c) {
            int v = s.tiles[r * 3 + c];
            if (v == 0) std::cout << ". ";
            else std::cout << v << " ";
        }
        std::cout << "\n";
    }
}

// Rekonstruksi jalur dari start ke goal via parent map.
std::vector<State> reconstruct(const State& start, const State& goal,
                               const ParentMap& parent) {
    std::vector<State> path;
    State cur = goal;
    while (cur != start) {
        path.push_back(cur);
        auto it = parent.find(cur);
        if (it == parent.end()) return {};   // tidak terjangkau
        cur = it->second;
    }
    path.push_back(start);
    std::reverse(path.begin(), path.end());
    return path;
}

// BFS: kembalikan jumlah node yang dikunjungi + jalur.
struct SearchResult {
    bool found;
    int nodesVisited;
    std::vector<State> path;
};

SearchResult bfs(const State& start, const State& goal) {
    std::queue<State> q;
    StateSet visited;
    ParentMap parent;

    q.push(start);
    visited.insert(start);
    parent[start] = start;

    int nodes = 0;
    while (!q.empty()) {
        State cur = q.front(); q.pop();
        nodes++;
        if (cur == goal) {
            return {true, nodes, reconstruct(start, goal, parent)};
        }
        for (const auto& nb : getNeighbors(cur)) {
            if (!visited.count(nb)) {
                visited.insert(nb);
                parent[nb] = cur;
                q.push(nb);
            }
        }
    }
    return {false, nodes, {}};
}

SearchResult dfs(const State& start, const State& goal, int maxDepth) {
    std::stack<std::pair<State, int>> st;
    StateSet visited;
    ParentMap parent;

    st.push({start, 0});
    visited.insert(start);
    parent[start] = start;

    int nodes = 0;
    while (!st.empty()) {
        auto [cur, d] = st.top(); st.pop();
        nodes++;
        if (cur == goal) {
            return {true, nodes, reconstruct(start, goal, parent)};
        }
        if (d + 1 > maxDepth) continue;          // jangan ekspansi lebih dalam
        for (const auto& nb : getNeighbors(cur)) {
            if (!visited.count(nb)) {
                visited.insert(nb);
                parent[nb] = cur;
                st.push({nb, d + 1});
            }
        }
    }
    return {false, nodes, {}};
}

void printPath(const std::vector<State>& path) {
    for (size_t i = 0; i < path.size(); ++i) {
        std::cout << "Langkah " << i << ":\n";
        print(path[i]);
        if (i + 1 < path.size()) std::cout << "\n";
    }
}

int main() {
    State start{{{1, 2, 3, 4, 0, 6, 7, 5, 8}}};

    std::cout << "State awal:\n";
    print(start);
    std::cout << "\nState goal:\n";
    print(GOAL);
    std::cout << "\n";

    std::cout << "=== BFS ===\n";
    auto bfsResult = bfs(start, GOAL);
    std::cout << "Ditemukan: " << (bfsResult.found ? "ya" : "tidak") << "\n";
    std::cout << "Node dikunjungi: " << bfsResult.nodesVisited << "\n";
    std::cout << "Panjang jalur: " << (bfsResult.path.size() - 1) << "\n\n";
    printPath(bfsResult.path);

    std::cout << "\n=== DFS ===\n";
    auto dfsResult = dfs(start, GOAL, 5);
    std::cout << "Ditemukan: " << (dfsResult.found ? "ya" : "tidak") << "\n";
    std::cout << "Node dikunjungi: " << dfsResult.nodesVisited << "\n";
    std::cout << "Panjang jalur: " << (dfsResult.path.size() - 1) << "\n\n";
    printPath(dfsResult.path);

    return 0;
}

Output yang Dihasilkan:

text
State awal:
1 2 3 
4 . 6 
7 5 8 

State goal:
1 2 3 
4 5 6 
7 8 . 

=== BFS ===
Ditemukan: ya
Node dikunjungi: 9
Panjang jalur: 2

Langkah 0:
1 2 3 
4 . 6 
7 5 8 

Langkah 1:
1 2 3 
4 5 6 
7 . 8 

Langkah 2:
1 2 3 
4 5 6 
7 8 . 

=== DFS ===
Ditemukan: ya
Node dikunjungi: 37
Panjang jalur: 2

Langkah 0:
1 2 3 
4 . 6 
7 5 8 

Langkah 1:
1 2 3 
4 5 6 
7 . 8 

Langkah 2:
1 2 3 
4 5 6 
7 8 . 

Pada kasus uji ini, BFS mengunjungi 9 node untuk menemukan solusi optimal 2 langkah, sedangkan DFS dengan maxDepth=5 mengunjungi 37 node — 4 kali lebih banyak. DFS tidak bisa “tahu” arah menuju goal, sehingga banyak mengunjungi state yang menjauh sebelum akhirnya menemukan jalur kembali ke goal. Untuk state yang lebih jauh, perbedaan ini akan semakin besar, dan itulah yang akan kita potong dengan A* di Bagian 4.

Bedah Kode Baris-per-Baris #

std::queue<State> q; q.push(start): antrian FIFO untuk BFS. front() membaca elemen paling awal; pop() menghapus elemen paling awal. Jaminan urutan level-by-level.
StateSet visited: set state yang sudah masuk queue. Tujuannya: cegah duplikat. Tanpa visited, BFS akan loop tak terhingga karena graph bisa berisi cycle (swap balik).
ParentMap parent: map state ke parent-nya. Saat sukses, kita bisa backtrack dari goal ke start melalui parent chain untuk merekonstruksi jalur.
if (cur == goal) return {true, nodes, reconstruct(...)}: early exit. BFS bisa berhenti segera setelah goal ditemukan, tanpa harus memproses seluruh queue. Inilah alasan BFS lebih cepat dari worst case O(V).
for (const auto& nb : getNeighbors(cur)): loop tetangga. const auto& menghindari copy struct.
if (!visited.count(nb)): cek apakah state sudah dikunjungi. Bila belum, masukkan ke visited, catat parent, dan tambah ke queue. Bila sudah, skip — tidak ada gunanya memproses state yang sama dua kali.
std::vector<State> reconstruct(...): backtrack dari goal ke start melalui parent. Mulai dari cur = goal, push ke path, lalu cur = parent[cur]. Loop sampai cur == start. Terakhir, reverse path agar urut dari start ke goal.
std::stack<std::pair<State, int>> st; st.push({start, 0}): stack LIFO untuk DFS, menyimpan (state, depth). top() membaca elemen paling akhir; pop() menghapus elemen paling akhir. DFS akan mendalami jalur yang paling baru ditambahkan. Field int untuk depth memungkinkan kita membatasi eksplorasi.
if (d + 1 > maxDepth) continue: depth limit. Bila kedalaman saat ini sudah mencapai batas, kita tidak menambah tetangga baru ke stack. Tanpa batas ini, DFS bisa mengunjungi ribuan state pada puzzle yang lebih dalam.
struct SearchResult { bool found; int nodesVisited; std::vector<State> path; }: kumpulan hasil. Memudahkan return tanpa tuple atau out-parameter. Field bisa diakses dengan sintaks titik (result.found).

Perbandingan BFS vs DFS #

Aspek	BFS	DFS
Struktur data	`std::queue` (FIFO)	`std::stack` (LIFO)
Kompleksitas waktu	O(V + E)	O(V + E)
Kompleksitas memori	O(V) — queue menyimpan level terlebar	O(depth) — stack menyimpan jalur saat ini
Optimalitas	Ya (pada bobot seragam)	Tidak
Complete (selalu nemu solusi)	Ya (pada finite graph)	Ya (bila ada depth limit)
Kapan dipakai	Cari jalur terpendek	Eksplorasi cepat, konsumsi memori rendah

Untuk 8-puzzle, BFS adalah pilihan utama karena optimal. A* (Bagian 4) akan menambahkan heuristic untuk memotong node yang tidak perlu dikunjungi.

Kompilasi dan Pengujian #

bash
g++ -std=c++17 -O2 -Wall -Wextra -o puzzle_part3.bin puzzle_part3.cpp
./puzzle_part3.bin

Verifikasi bahwa BFS menemukan jalur 2 langkah, dan DFS juga menemukan jalur 2 langkah (karena goal dekat). Coba ubah state awal ke 1 3 4 8 0 5 7 2 6 — jalur BFS akan lebih panjang (sekitar 6 langkah), dan DFS mungkin menemukan jalur berbeda yang lebih panjang.