Abstract:
Ada beberapa metode untuk menentukan semua minimum spanning tree pada graf terhubung dengan pembobotan. Salah satu metode adalah menggunakan algoritma kruskal yang diperluas. Algoritma Kruskal hanya dapat menentukan satu bentuk minimum spanning tree saja. Metode ini diperluas dengan cara menukar salah satu sisi pada minimum spanning tree dengan sisi lain pada graf tetapi tidak masuk pada minimum spanning tree yang bobotnya sama. Bila hasil penukaran sisi tersebut tidak membentuk cycle dengan sisi lain pada minimum spanning tree, maka akan terbentuk minimum spanning tree yang baru dengan satu sisi yang berbeda. Akan tetapi bila membentuk cycle, maka sisi tersebut tidak membentuk minimum spanning tree. Hal ini dilakukan untuk semua sisi yang bobotnya sama. Metode yang dilakukan ini disebut dengan Algortima kruskal yang diperluas
