Penggunaan Algoritma Kruskal yang Diperluas untuk Mencari Semua Minimum Spanning Tree Tanpa Konstren dari Suatu Graf
No Thumbnail Available
Date
2018-02-19
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
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
Description
Keywords
Spanning tree, algoritma Kruskal, pergantian sisi, minimum spanning trees, graf dengan pembobotan