(Teori Graf) Mencari Pohon Merentang Minimum dengan Algoritma Kruskal dalam Bahasa C++
Algoritma Kruskal Sumber gambar: http://lukmanreza.blogspot.com/ Algoritma Kruskal adalah sebuah algoritma dalam teori graf yang mencari sebuah minimum spanning tree (MST) untuk sebuah graf berbobot yang terhubung. Langkah Algoritma Kruskal: 1. Lakukan pengurutan terhadap setiap sisi di graf mulai dari sisi yang memiliki bobot terkecil. 2. Pilih sisi yang mempunyai bobot minimum yang tidak membentuk sirkuit pada pohon, kemudian tambahkan sisi tersebut ke dalam pohon. 3. Ulangi langkah kedua sebanyak n – 1 kali (n adalah jumlah simpul graf). Dalam pembuatan graf algoritma kruskal lintasannya tidak boleh membentuk circle. Kelebihan Dan Kekurangan Algoritma Kruskal 1. Kelebihan Sangat cocok digunakan saat graf memiliki sisi berjumlah sedikit namun memiliki sangat banyak simpul, karena orientasi kerja algoritma ini adalah berdasarkan urutan bobot sisi bukan simpul. 2. Kekurangan Kurang cocok digunakan saat graf dimana setiap simpul terhubungkan dengan s