Dalam dunia ilmu komputer dan optimasi jaringan, konsep Pohon Rentang Minimum atau Minimum Spanning Tree (MST) merupakan salah satu topik yang paling krusial. Baik Anda seorang mahasiswa teknik informatika yang sedang menghadapi ujian algoritma, maupun seorang praktisi yang ingin mengoptimalkan infrastruktur jaringan, memahami MST adalah sebuah keharusan.
Artikel ini akan membahas secara mendalam mengenai apa itu Pohon Rentang Minimum, algoritma-algoritma utama yang digunakan untuk menyelesaikannya, serta kumpulan contoh soal yang disertai pembahasan langkah demi langkah agar Anda benar-benar menguasai materi ini.
Baca juga: Contoh Soal PSAK 1 Lengkap dengan Pembahasan Laporan Keuangan
Apa Itu Pohon Rentang Minimum (MST)?
Sebelum masuk ke contoh soal, kita perlu menyamakan persepsi mengenai definisi MST. Bayangkan Anda memiliki sekumpulan kota yang ingin dihubungkan dengan kabel serat optik. Setiap jalur antar kota memiliki biaya (bobot) tertentu. Tujuan Anda adalah menghubungkan semua kota sehingga:
- Semua kota terhubung satu sama lain (langsung maupun tidak langsung).
- Tidak ada sirkuit atau loop yang terbentuk.
- Total biaya kabel yang digunakan adalah yang paling minimum.
Dalam terminologi graf, MST adalah subgraph dari graf berbobot, terhubung, dan tidak berarah yang menghubungkan semua simpul (vertex) dengan total bobot sisi (edge) terkecil.
Dua Algoritma Utama: Prim dan Kruskal
Ada dua algoritma yang paling populer dan sering keluar dalam soal ujian untuk mencari MST:
1. Algoritma Prim
Algoritma ini bekerja secara “tumbuh” dari satu simpul awal. Ia akan selalu memilih sisi dengan bobot terkecil yang menghubungkan simpul yang sudah terpilih dengan simpul yang belum terpilih.
- Kelebihan: Sangat efisien untuk graf yang padat (dense graph).
- Strategi: Berorientasi pada simpul (vertex-oriented).
2. Algoritma Kruskal
Algoritma ini bekerja dengan cara mengurutkan semua sisi dari yang terkecil hingga terbesar. Sisi diambil satu per satu asalkan tidak membentuk siklus (cycle).
- Kelebihan: Lebih mudah dipahami secara intuitif dan efisien untuk graf yang jarang (sparse graph).
- Strategi: Berorientasi pada sisi (edge-oriented).
Contoh Soal 1: Dasar Algoritma Kruskal
Soal:
Diberikan sebuah graf dengan simpul {A, B, C, D} dan sisi-sisi sebagai berikut:
- (A, B) dengan bobot 4
- (A, C) dengan bobot 1
- (B, C) dengan bobot 2
- (B, D) with bobot 5
- (C, D) with bobot 8
Tentukan Pohon Rentang Minimum menggunakan algoritma Kruskal!
Pembahasan:
Langkah 1: Urutkan semua sisi berdasarkan bobot terkecil ke terbesar.
- (A, C) – Bobot: 1
- (B, C) – Bobot: 2
- (A, B) – Bobot: 4
- (B, D) – Bobot: 5
- (C, D) – Bobot: 8
Langkah 2: Pilih sisi satu per satu tanpa membentuk siklus.
- Pilih (A, C) bobot 1. (Terpilih)
- Pilih (B, C) bobot 2. (Terpilih)
- Pilih (A, B) bobot 4. Jika kita menghubungkan A dan B, maka akan terbentuk siklus A-C-B-A. Jadi, sisi (A, B) ditolak.
- Pilih (B, D) bobot 5. (Terpilih)
Langkah 3: Hitung Total Bobot.
Karena semua simpul (A, B, C, D) sudah terhubung, proses berhenti.
Total MST = $1 + 2 + 5 = 8$.
Contoh Soal 2: Implementasi Algoritma Prim
Soal:
Gunakan Algoritma Prim pada graf yang sama dengan soal nomor 1, dimulai dari simpul A.
Pembahasan:
Langkah 1: Mulai dari simpul A.
Sisi yang terhubung dengan A adalah (A, B) bobot 4 dan (A, C) bobot 1.
Pilih yang terkecil: (A, C) dengan bobot 1. Sekarang simpul yang terhubung adalah {A, C}.
Langkah 2: Cari sisi terkecil dari simpul {A, C} ke simpul yang belum terhubung {B, D}.
Opsi:
- (A, B) bobot 4
- (C, B) bobot 2
- (C, D) bobot 8Pilih yang terkecil: (C, B) dengan bobot 2. Sekarang simpul yang terhubung adalah {A, C, B}.
Langkah 3: Cari sisi terkecil dari simpul {A, C, B} ke simpul yang belum terhubung {D}.
Opsi:
- (B, D) bobot 5
- (C, D) bobot 8Pilih yang terkecil: (B, D) dengan bobot 5.
Hasil Akhir:
Total Bobot = $1 + 2 + 5 = 8$.
Hasilnya sama dengan algoritma Kruskal, namun urutan pemilihannya berbeda.
Contoh Soal 3: Studi Kasus Jaringan Listrik Desa
Soal:
Sebuah perusahaan listrik ingin membangun jaringan kabel di 5 dusun (P, Q, R, S, T). Berikut adalah estimasi biaya pembangunan kabel antar dusun (dalam jutaan Rupiah):
- P-Q: 10
- P-S: 5
- Q-R: 1
- Q-S: 3
- R-S: 9
- R-T: 6
- S-T: 2
Berapakah biaya minimum untuk menghubungkan kelima dusun tersebut?
Pembahasan (Menggunakan Kruskal):
- Urutkan Sisi:
- Q-R (1)
- S-T (2)
- Q-S (3)
- P-S (5)
- R-T (6)
- R-S (9)
- P-Q (10)
- Pemilihan Sisi:
- Ambil Q-R (1).
- Ambil S-T (2).
- Ambil Q-S (3). (Menghubungkan {Q, R} dan {S, T})
- Ambil P-S (5). (Menghubungkan P ke jaringan yang sudah ada)
- Cek R-T (6): Jika diambil, akan terjadi siklus R-Q-S-T-R. Ditolak.
- Sisi lainnya sudah tidak diperlukan karena semua simpul sudah terhubung.
- Total Biaya:Total = $1 + 2 + 3 + 5 = 11$ juta Rupiah.
Perbedaan Karakteristik Prim dan Kruskal
Untuk membantu Anda memilih algoritma mana yang lebih mudah digunakan saat ujian, perhatikan tabel perbandingan berikut:
| Fitur | Algoritma Prim | Algoritma Kruskal |
| Fokus Utama | Simpul (Vertex) | Sisi (Edge) |
| Cara Kerja | Menambah simpul tetangga terdekat | Menambah sisi terpendek global |
| Pengecekan Siklus | Tidak perlu (otomatis aman) | Perlu pengecekan sirkuit |
| Kondisi Graf | Efektif untuk graf padat | Efektif untuk graf renggang |
Mengapa Pohon Rentang Minimum Penting?
Dalam SEO dan optimasi konten, relevansi adalah kunci. Begitu pula dengan MST. Pengaplikasiannya sangat luas di dunia nyata:
- Desain Jaringan Telekomunikasi: Menghemat biaya kabel tembaga atau fiber.
- Jaringan Transportasi: Membangun rute jalan raya yang menghubungkan semua kota dengan panjang jalan minimum.
- Analisis Cluster: Dalam data mining, MST digunakan untuk mengelompokkan data yang memiliki kemiripan tinggi.
- Protokol Spanning Tree (STP): Dalam jaringan komputer (Switching), protokol ini mencegah terjadinya looping yang bisa mematikan jaringan.
Tips Mengerjakan Soal Pohon Rentang Minimum
- Gambarkan Graf Terlebih Dahulu: Jangan hanya mengandalkan daftar angka. Visualisasi membantu Anda melihat potensi siklus dengan lebih cepat.
- Coret Sisi yang Ditolak: Saat menggunakan Kruskal, berikan tanda silang pada sisi yang menyebabkan siklus agar Anda tidak bingung di langkah berikutnya.
- Hitung Jumlah Sisi: Jika jumlah simpul adalah $n$, maka jumlah sisi pada MST haruslah $n – 1$. Jika Anda mendapatkan lebih atau kurang, berarti ada kesalahan.
- Periksa Kembali Siklus: Ini adalah kesalahan paling umum. Pastikan tidak ada jalur tertutup di hasil akhir Anda.
Contoh Soal 4: Graf dengan Bobot Sama
Soal:
Apa yang terjadi jika sebuah graf memiliki beberapa sisi dengan bobot yang sama? Apakah MST yang dihasilkan akan selalu unik?
Pembahasan:
Jika sebuah graf memiliki sisi-sisi dengan bobot yang sama, maka Pohon Rentang Minimum belum tentu unik. Anda mungkin bisa mendapatkan dua atau lebih bentuk pohon yang berbeda, tetapi total bobot akhirnya akan tetap sama dan tetap minimum.
Misal: Simpul A, B, C membentuk segitiga sama sisi dengan semua bobot = 5.
- MST 1: Pilih (A,B) dan (B,C). Total = 10.
- MST 2: Pilih (A,C) dan (B,C). Total = 10.Keduanya adalah MST yang valid.
Baca juga: Universitas Teknokrat Indonesia Peringati Isra Mi’raj Perdana di Masjid Agung Al Hijrah Kota Baru
Penutup
Memahami Pohon Rentang Minimum bukan hanya soal menghitung angka, melainkan tentang logika efisiensi. Dengan menguasai Algoritma Prim dan Kruskal melalui latihan soal di atas, Anda akan lebih siap menghadapi persoalan struktur data maupun optimasi jaringan.
Penulis: Aripin
Post Comment