Definisi spanning tree
Rentang pohon terdiri dari semua node dalam graf dan beberapa edge sehingga semua node saling terhubung. Spanning Tree merupakan graf tehubung yang diperoleh dari meutus sirkuit dalam graf. Bobot spanning tree adalah jumlahan dari bobot tepi.
Gambar 1. Graf Gambar 2. Rentang Pohon berbobot 22
Dengan demikian, Pohon Rentang Minimum adalah graf yang diperoleh dari memutus sirkuit dalam graf, tidak memiliki arah, dan memiliki bobot paling minimal .
Gambar 3. Rentang pohon minimal berbobot 20
Ada beberapa algoritma untuk memperoleh Minimum Spanning Tree, yaitu:
- Prim
Langkah-langkah:
- Ambil edge (T) dengan bobot tulang pada pohon.
- Ambil edge yang bersisian dengan node di T dengan bobot minimum yang menambah node baru (tidak membentuk sirkuit) pada Tree.
- Ulangi langkah 2 sebanyak n-2 kali.
- Kruskal
Langkah-langkah:
- Graf pada awalnya hanya terdiri dari node saja.
- Tambahkan tepi berdasarkan bobot yang paling kecil dan tepi yang ditambahkan tidak membentuk sirkuit.
- Ulangi langkah 2 sebanyak n-1 kali.
Mempelajari algoritma tentu tidak lengkap tanpa adanya latihan, berikut beberapa latihan yang dapat digunakan untuk mengimplementasikannya:
https://www.omahti.web.id/
