Sistem Pencarian Jalur pada Labirin

Topik 9 — Breadth First Search (BFS) vs Depth First Search (DFS)

Project Akhir Mata Kuliah Analisis Algoritma
Program Studi Ilmu Komputer — Universitas Putra Bangsa
Dosen Pengampu: Awaludin Abid, S.Kom., M.Kom.

---

Anggota Kelompok 10

Nama	NIM
Rafi Nurul Fauzan	250202961
Fatkhurrohman Gilang Ramadhan	250202985
Muhammad Fajri Abdullah	250202979

---

Deskripsi

Program CLI (Command Line Interface) berbasis Python untuk membuat labirin berbasis Grid/Matrix, mencari jalur dari titik awal ke tujuan menggunakan dua algoritma, dan membandingkan performa keduanya secara eksperimental.

Komponen	Detail
Algoritma 1	Breadth First Search (BFS) — menggunakan Queue (FIFO)
Algoritma 2	Depth First Search (DFS) — menggunakan Stack (LIFO)
Struktur Data 1	Queue via collections.deque
Struktur Data 2	Stack via list Python
Representasi labirin	Grid/Matrix 2D (0 = jalur, 1 = dinding)

---

Struktur Folder

SistemPencarianJalurLabirin/
├── main.py              → Menu utama & loop program
├── algorithms.py        → Implementasi BFS dan DFS
├── maze_generator.py    → Generator dan tampilan labirin
├── data_ops.py          → Operasi CRUD labirin (tambah/ubah/hapus/simpan/baca)
├── experiment.py        → Eksperimen performa, CSV, grafik, rekomendasi
├── interactive.py       → Mode demo visual dan edit interaktif
├── maze_50.txt          → Dataset labirin ~50 sel aktif
├── maze_100.txt         → Dataset labirin ~100 sel aktif
├── maze_250.txt         → Dataset labirin ~250 sel aktif
├── maze_500.txt         → Dataset labirin ~500 sel aktif
├── maze_custom.txt      → Labirin hasil edit manual (dibuat saat program berjalan)
└── README.md

---

Prasyarat

Pastikan sudah terpasang di komputer:

• Python 3.8 atau lebih baru

  python --version

• pip (biasanya sudah termasuk bersama Python)

  pip --version

• Git (untuk clone dari GitHub)

  git --version

---

Cara Menjalankan

Langkah 1 — Clone Repository

Buka terminal (Command Prompt / PowerShell / Terminal), lalu jalankan:

git clone https://github.com/<username>/<nama-repo>.git

Masuk ke folder project:

cd <nama-repo>

Ganti <username> dan <nama-repo> sesuai dengan link repository kamu.

---

Langkah 2 — Install Dependensi

Program hanya membutuhkan satu library tambahan (untuk fitur grafik):

pip install matplotlib

Jika tidak ingin menggunakan fitur grafik, langkah ini bisa dilewati.
Program tetap berjalan normal — hanya menu grafik yang akan dilewati otomatis.

---

Langkah 3 — Jalankan Program

python main.py

---

Menjalankan di VS Code

1. Buka folder project di VS Code:

   • Pilih menu File → Open Folder
   • Arahkan ke folder hasil clone tadi → klik Select Folder

2. Buka terminal di VS Code:

   • Tekan Ctrl + ` (backtick) atau pilih menu Terminal → New Terminal

3. Install dependensi (jika belum):

   pip install matplotlib

4. Jalankan program:

   python main.py

5. (Opsional) Jalankan file secara langsung dari editor:

   • Buka file main.py di editor
   • Klik tombol ▶ Run Python File di pojok kanan atas
   • Atau tekan Ctrl + F5

Catatan: Pastikan interpreter Python yang dipilih di VS Code sudah benar.
Cek di pojok kiri bawah — klik untuk ganti jika perlu.

---

Menu Program

Setelah program berjalan, akan muncul menu berikut:

====================================================
  SISTEM PENCARIAN JALUR LABIRIN  |  TOPIK 9
====================================================
  1. Demo pencarian (visualisasi labirin)
  2. Eksperimen lengkap (4 skala x 5 ulangan)
  3. Eksperimen + simpan CSV + grafik
  4. Edit labirin manual (tambah/ubah/hapus dinding) + uji BFS/DFS
  5. Muat labirin dari file (.txt) + uji BFS/DFS
  6. Uji performa custom (ukuran sel aktif bebas)
  0. Keluar
----------------------------------------------------

Menu	Fungsi	Output
1	Pilih ukuran labirin (10×10 / 15×15 / 20×20 / custom), tampilkan hasil BFS & DFS secara visual	Tampilan labirin + jalur ditemukan
2	Eksperimen otomatis 4 skala (50/100/250/500 sel aktif), 5 ulangan + rekomendasi	Tabel di terminal
3	Sama seperti menu 2, ditambah simpan hasil ke file	hasil_eksperimen.csv + grafik_waktu_eksekusi.png
4	Buat labirin, tambah/hapus dinding secara manual, simpan ke file, uji BFS & DFS	Tampilan labirin + hasil pencarian
5	Pilih file .txt yang sudah ada, muat labirinnya, langsung uji BFS & DFS	Tampilan labirin + hasil pencarian
6	Masukkan ukuran sel aktif bebas (misal 300), uji BFS & DFS — cocok untuk demo presentasi	Tabel + rekomendasi
0	Keluar dari program	—

---

Output yang Dihasilkan

File	Dibuat oleh	Isi
hasil_eksperimen.csv	Menu 3	Waktu eksekusi per uji, rata-rata, panjang jalur, sel diperiksa
grafik_waktu_eksekusi.png	Menu 3	Grafik perbandingan waktu eksekusi + sel diperiksa BFS vs DFS
maze_custom.txt	Menu 4 (simpan)	Labirin hasil edit manual

---

🔍 Legenda Tampilan Labirin

S  →  Titik awal (start)
G  →  Titik tujuan (goal)
.  →  Jalur yang bisa dilalui
#  →  Dinding / hambatan
*  →  Jalur hasil pencarian BFS atau DFS

---

Algoritma dan Kompleksitas

Algoritma	Struktur Data	Kompleksitas Waktu	Kompleksitas Ruang	Jamin Jalur Terpendek?
BFS	Queue (deque, FIFO)	O(V + E)	O(V)	Ya
DFS	Stack (list, LIFO)	O(V + E)	O(V)	Tidak selalu

V = jumlah sel aktif, E = jumlah hubungan antar sel (maksimum 4 per sel)

---

Skala Data Pengujian

Skala (sel aktif)	Grid (approx)	File dataset
50	~9 × 9	maze_50.txt
100	~12 × 12	maze_100.txt
250	~19 × 19	maze_250.txt
500	~27 × 27	maze_500.txt

---

Catatan Tambahan

• BFS menjamin jalur terpendek karena menjelajahi labirin secara berlapis (level by level).
• DFS tidak menjamin jalur terpendek, namun pada banyak kasus lebih cepat karena langsung menelusuri satu arah secara mendalam.
• Semua eksperimen menggunakan seed yang konsisten agar BFS dan DFS diuji pada labirin yang identik dan hasil dapat direproduksi.
• Dataset labirin (file .txt) dapat diedit manual melalui menu 4, atau dibuat ulang otomatis oleh program.