Minimum spanning Tree

Graph : kumpulan dua himpunan yaitu himpunan titik ( vertex / simpul / node ) dan kumpulan dari garis ( edge )

Tree : graph tak berarah yang terhubung dan tidak mengandung sirkuit.

Sirkuit : simpul awal = simpul akhir

Contoh : Pandang sebuah graph sebagai berikut;

Algoritma Kruskall

Dasar pembentukan algoritma Kruskal berasal dari analogi growing forest. Growing forest maksudnya adalah untuk membentuk pohon merentang minimum T dari grafG adalah dengan cara mengambil satu per satu sisi dari graf G dan memasukkannya ke dalam pohon yang telah terbentuk sebelumnya. Seiring dengan berjalannya iterasi untuk setiap sisi, maka forest akan memiliki pohon yang semakin sedikit. Oleh sebab itu, maka analogi ini disebut dengan growing forest. Algoritma Kruskal akan terus menambahkan sisi – sisi ke dalam hutan yang sesuai hingga akhirnya tidak akan ada lagi forest dengan, melainkan hanyala