Tugas Besar 2 IF2211 Strategi Algoritma — Semester II 2025/2026
Program Studi Teknik Informatika, STEI — Institut Teknologi Bandung
Aplikasi web untuk menelusuri elemen HTML pada struktur pohon Document Object Model (DOM) menggunakan algoritma Breadth-First Search (BFS) dan Depth-First Search (DFS) berdasarkan CSS Selector. Aplikasi dapat menerima input berupa URL website atau HTML mentah, lalu menampilkan visualisasi pohon DOM beserta animasi proses penelusuran secara real-time.
BFS menelusuri pohon DOM secara melebar, mengunjungi seluruh node pada satu level (kedalaman) sebelum berpindah ke level berikutnya. Implementasi menggunakan antrian (queue) dengan prinsip FIFO. Dimulai dari root <html>, seluruh anak-anaknya dimasukkan ke antrian, kemudian diproses satu per satu sambil memasukkan anak-anak mereka ke antrian, hingga antrian kosong atau batas hasil tercapai.
Multithreading pada BFS: Setiap level pohon diproses secara paralel menggunakan goroutine dan sync.WaitGroup. Seluruh node dalam satu level diperiksa secara bersamaan, hasil dikumpulkan, lalu dilanjutkan ke level berikutnya.
Karakteristik: Menemukan elemen di level paling dangkal terlebih dahulu. Cocok untuk mencari elemen yang dekat dengan root seperti <header> atau <nav>.
DFS menelusuri pohon DOM secara mendalam, menyelami satu cabang hingga ujung sebelum backtrack dan menjelajahi cabang lainnya. Implementasi menggunakan rekursi pre-order: mengunjungi node saat ini terlebih dahulu, kemudian secara rekursif mengunjungi setiap subtree anak dari kiri ke kanan.
Multithreading pada DFS: Subtree dari setiap anak root diproses secara paralel oleh goroutine terpisah. Hasil digabungkan kembali dalam urutan pre-order asli menggunakan channel dan sorting berdasarkan childIdx.
Karakteristik: Menghasilkan urutan yang sesuai dengan kemunculan elemen dalam dokumen HTML. Cocok untuk elemen yang bersarang dalam (deeply nested).
Fitur tambahan untuk menentukan Lowest Common Ancestor (LCA) — elemen HTML terdekat yang menjadi parent bersama dari dua elemen yang dipilih. Preprocessing O(N log N) menggunakan tabel sparse table[v][k] yang menyimpan ancestor ke-2^k dari node v, memungkinkan query LCA dalam O(log N).
- Go >= 1.22
- Dependensi eksternal:
github.com/rs/cors v1.11.0 - Tidak menggunakan library parsing HTML eksternal — tokenizer dan tree builder diimplementasikan sendiri
- Node.js >= 18
- npm >= 9
- Docker >= 24
- Docker Compose >= 2
# Masuk ke folder backend
cd backend
# Download dependencies
go mod tidy
# Jalankan langsung
go run main.go
# ATAU build binary terlebih dahulu
go build -o tubes2_backend ./main.go
./tubes2_backendBackend berjalan di http://localhost:8080
# Masuk ke folder frontend
cd frontend
# Install dependencies
npm install
# Jalankan development server
npm run devFrontend berjalan di http://localhost:5173
Buka browser dan akses http://localhost:5173
Pastikan Docker Desktop sudah berjalan, lalu dari root folder proyek:
# Build dan jalankan semua service sekaligus
docker compose up --build
# Atau jalankan di background
docker compose up --build -dTunggu hingga build selesai (~5-10 menit pertama kali), lalu buka browser:
http://localhost
Untuk menghentikan:
docker compose downAplikasi sudah di-deploy dan dapat diakses langsung tanpa instalasi apapun:
http://tubes2-kasifaham.eastasia.cloudapp.azure.com
- Masukkan sumber HTML — pilih antara URL website (akan di-scrape otomatis) atau paste HTML mentah langsung
- Pilih algoritma — BFS atau DFS
- Masukkan CSS Selector — contoh:
p.text,div > h1,#main .container,h1 ~ p - Tentukan jumlah hasil — top-n (masukkan angka) atau semua kemunculan (isi 0)
- Klik Traversal — animasi penelusuran akan berjalan secara real-time pada visualisasi pohon DOM
- Lihat hasil — daftar elemen yang cocok, jumlah node dikunjungi, waktu pencarian, dan log traversal
Tubes2_NamaKelompok/
├── docker-compose.yml
├── README.md
├── backend/
│ ├── main.go
│ ├── go.mod
│ ├── Dockerfile
│ └── internal/
│ ├── models/
│ │ └── models.go
│ ├── parser/
│ │ ├── parser.go
│ │ ├── tokenizer.go
│ │ ├── selector.go
│ │ └── parser_test.go
│ ├── traversal/
│ │ ├── bfs_dfs.go
│ │ ├── lca.go
│ │ ├── traversal_test.go
│ │ └── lca_test.go
│ ├── scraper/
│ │ └── scraper.go
│ └── handler/
│ └── handler.go
└── frontend/
├── Dockerfile
├── nginx.conf
├── package.json
└── src/
├── App.tsx
├── api/
│ └── client.ts
└── components/
├── DomTree.tsx
├── SearchForm.tsx
└── TraversalLog.tsx
| Nama | NIM |
|---|---|
| Gabriella Botimada Lubis | 13524006 |
| Reva Natania Sitohang | 13524098 |