PEDIA: Algoritma Kruskal |

<p><br />
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-indent: .5in;">
<b><span style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">H</span></b><b><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">. Algoritma Menentukan
Minimum Spanning Tree (MST)</span></b></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-indent: .5in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Dua algoritma populer
untuk menentukan minimum spanning tree (MST) </span><span style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">adalah
Kruskal Algorithm dan Prim’s Algorithm.</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in;">
<br /></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in;">
<b><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">1. Algoritma Kruskal</span></b><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify; text-indent: .5in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Algoritma
ini lebih sederhana jika dilihat dari konsepnya namun lebih sulit dalam
implementasinya. Idenya adalah mendapatkan satu demi satu sisi mulai dari yang
berbobot terkecil untuk membentuk tree</span><span style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">,</span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";"> suatu sisi walaupun berbobot kecil tidak
akan diambil jika membentuk siklik dengan sisi yang sudah termasuk dalam
tree. Yang menjadi masalah dalam implementasinya adalah keperluan adanya
pemeriksaan kondisi siklik tersebut.Salah satu pemecahaannya adalah dengan
subsetting yaitu pembentukan subset-subset yang disjoint dan secara
bertahap dilakukan penggabungan atas tiap dua subset yang berhubungan dengan
suatu sisi dengan bobot terpendek. Algoritma lengkapnya:</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify;">
<br /></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-indent: -.25in;">
<span lang="IN" style="color: #262626; font-family: Symbol; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">·</span><span lang="IN" style="color: #262626; font-family: "Times New Roman","serif"; font-size: 7.0pt; mso-ansi-language: IN; mso-fareast-font-family: "Times New Roman";">         </span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Tahap pertama, jika dalam V terdapat n verteks maka
diinisialisasi n buah subset yang disjoint, masing-masing berisi satu verteks,
sebagai subset-subset awal.</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-indent: -.25in;">
<span lang="IN" style="color: #262626; font-family: Symbol; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">·</span><span lang="IN" style="color: #262626; font-family: "Times New Roman","serif"; font-size: 7.0pt; mso-ansi-language: IN; mso-fareast-font-family: "Times New Roman";">         </span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Tahap berikutnya, urutkan sisi-sisi dengan bobot yang
terkecil hingga terbesar.</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-indent: -.25in;">
<span lang="IN" style="color: #262626; font-family: Symbol; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">·</span><span lang="IN" style="color: #262626; font-family: "Times New Roman","serif"; font-size: 7.0pt; mso-ansi-language: IN; mso-fareast-font-family: "Times New Roman";">         </span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Mulai dari sisi dengan bobot terkecil hingga terbesar
lakukan dalam iterasi: jika sisi tsb. menghubungkan dua vertex dalam satu
subset (berarti membentuk siklik) maka skip sisi tersebut dan periksa sisi
berikutnya jika tidak (berarti membentuk siklik) maka kedua subset dari
verteks-verteks yang bersangkutan digabungkan menjadi satu subset yang lebih
besar. Iterasi akan berlangsung hingga semua sisi terproses.</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span><br />
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";"><br /></span>
<div style="text-align: center;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">

</span></div>
</div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in;">
</div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">MST_KRUSKAL (G)</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">{ For setiap vertex v dalam V[G] Do</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">{ set S(v) ← {v} }</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-indent: .5in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Inisialisasi priority
queue Q yang berisi semua edge dari G,</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">gunakan bobot sebagai keys.</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-indent: .5in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">A ← { } // A berisi edge
dari MST</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-indent: .5in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">While A lebih kecil dari
pada n-1 edge Do</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-indent: .5in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">{ set S(v) berisi v dan
S(u) berisi u }</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-indent: .5in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">IF S(v) != S(u) Then</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-indent: .5in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">{ Tambahkan edge (u, v)
ke A</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-indent: .5in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Merge S(v) dan S(u)
menjadi satu set</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-indent: .5in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">}</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-indent: .5in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Return A</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">}</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in;">
<b><span style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">2. </span></b><b><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Algoritma
Prim</span></b><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify; text-indent: .5in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Algoritma
dimulai dari suatu verteks awal tertentu dan bisa ditentukan oleh pemanggil
atau dipilih se</span><span style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">m</span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">barang oleh algoritma. Misalnya verteks
awal tersebut adalah v. Pada setiap iterasi terdapat kondisi di mana himpunan
vertex V terbagi dalam</span><span style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";"> dua</span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">:</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify;">
<i><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">W
yaitu himpunan verteks yang sudah dievaluasi sebagai node di dalam pohon, serta
(V-W) yaitu himpunan verteks yang belum dievaluasi.</span></i><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Di awal algoritma W
diinisialisasi berisi verteks awal v. Selanjutnya, di dalam iterasinya:</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify;">
<i><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Pada
setiap adjacency dari tiap verteks dalam W dengan verteks dalam (V-W) dicari
sisi dengan panjang minimal. setelah diperoleh, sisi tersebut ditandai sebagai
sisi yang membentuk tree dan verteks adjacent sisi tersebut dalam (VW)
dipindahkan ke W (menjadi anggota W).</span></i><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify; text-indent: .5in;">
<span style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">J</span><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">ika sisi tersebut tidak ada maka proses selesai.</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify; text-indent: .5in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 12.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">Dari
contoh di atas misalnya dilakukan pencarian mulai dari verteks A Maka algoritma
ini menghasilkan tahapan-tahapan iterasi pencarian sbb.:</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-align: justify;">
<br /></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">MST_PRIM (G, w, v)</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">{ Q ← V[G]</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-indent: .5in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">for setiap u dalam Q do
key [u] ← ∞</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-indent: .5in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">key [r] ← 0</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-indent: .5in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">π[r] ← NIl</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-indent: .5in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">while queue tidak kosong
do</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-indent: .5in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">{ u ← EXTRACT_MIN (Q)</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-indent: .5in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">for setiap vertex v dalam
Adj[u] do</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-indent: .5in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">{ if v ada dalam Q dan
w(u, v) < key [v] then</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-indent: .5in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">{ π[v] ← w(u, v)</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></div>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-indent: .5in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">key [v] ← w(u, v)</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span><br />
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";"></span><br />
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-indent: .5in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";"><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">}</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></span></div>
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">

</span><br />
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in; text-indent: .5in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";"><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">}</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></span></div>
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">
</span>
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in;">
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";"><span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">}</span><span style="color: black; font-family: "Times New Roman","serif"; font-size: 13.5pt; mso-fareast-font-family: "Times New Roman";"><o:p></o:p></span></span></div>
<span lang="IN" style="color: #262626; font-family: ""sans-serif"","serif"; font-size: 10.0pt; mso-ansi-language: IN; mso-bidi-font-family: "Times New Roman"; mso-fareast-font-family: "Times New Roman";">
<div class="MsoNormal" style="line-height: 18.0pt; margin-bottom: .0001pt; margin-bottom: 0in;">
<br /></div>
</span></div>
</p>

H . Algoritma Menentukan Minimum Spanning Tree (MST) Dua algoritma populer untuk menentukan minimum spanning tree (MST) adalah Kruskal ...