Alpro Keren

GRAF DAN POHON

A. Pengertian Graf Dan Pohon

• Graf adalah salah satu jenis Struktur data yang terdiri dari titik (vertex) dan garis (edge), dimana dalam tersebut, vertex-vertex yang dihubungkan oleh edge, hingga menjadi suatu kesatuan yang disebut graf.
• Pohon adalah graph tak berarah yang terhubung dan tidak mengandung sirkuit.

B. Algoritma Graf Dan Pohon

1. Graf

• Beri nilai bobot (jarak) untuk setiap titik ke titik lainnya, lalu set nilai 0 pada node awal dan nilai tak hingga terhadap node lain (yang belum terisi).
•  Set semua node “Belum terjamah” dan set node awal sebagai “Node keberangkatan”.
• Dari node keberangkatan, pertimbangkan node tetangga yang belum terjamah dan hitung jaraknya dari titik keberangkatan.
• Setelah selesai mempertimbangkan setiap jarak terhadap node tetangga, tandai node yang telah terjamah sebagai “Node terjamah”. Node terjamah tidak akan pernah di cek kembali, jarak yang disimpan adalah jarak terakhir dan yang paling minimal bobotnya.
•  Set “Node belum terjamah” dengan jarak terkecil (dari node keberangkatan) sebagai “Node Keberangkatan” selanjutnya dan lanjutkan dengan kembali ke step 3.

2. Pohon

• T masih kosong .
• 2. pilih sisi (i,j) dengan bobot minimum.
• 3. pilih sisi (i,j) dengan bobot minimum berikutnya yang tidak membentuk
• cycle di T, tambahkan (i,j) ke T.
• 4. Ulangi langkah 3 sebanyak (n-2) kali.
• 5. Total langkah (n-1) kali

C. Contoh

1. Graf

2. Pohon