Algoritma Sollin

Algoritma Sollin menentukan pohon merentang minimum dengan cara melakukan penghapusan sisi yang tidak menyebabkan graf menjadi tidak terhubung atau membentuk sirkuit. Penghapusan tersebut dimulai dari sisi yang memiliki bobot terbesar hingga terkecil. Penghapusan dilakukan setelah sebelumnya sisi-sisi pada graf diurutkan berdasarkan bobotnya dari besar ke kecil.

Langkah-langkah dalam algoritma Sollin adalah sebagai berikut:

1.      Urutkan sisi pada graf berdasarkan bobotnya dari besar ke kecil.

2.      Lakukan penghapusan setiap sisi dimulai dari bobot yang terbesar yang tidak menyebabkan graf menjadi tidak terhubung.

3.   Ulangi langkah 2 sampai pohon merentang minimum terbentuk, yaitu ketika sisi di dalam pohon merentang minimum berjumlah n-1 (n adalah jumlah simpul di graf).

Berdasarkan gambar di atas, maka pengurutan sisi pada graf mulai dari sisi dengan bobot terbesar sampai bobot terkecil dapat dilihat pada tabel berikut:

Bobot	Sisi
50	(E,G)
48	(E,F)
45	(C,E)
40	(A,B)
35	(A,D)
30	(D,E)
25	(B,E)
20	(D,H)
15	(A,C)
14	(G,H)
10	(F,G)

Untuk lebih memahami cara kerja algoritma Sollin, maka dari gambar di atas dapat dicari pohon merentang minimumnya dengan menggunakan algoritma tersebut. Langkah-langkah pembentukan pohon merentang minimumnya dapat dilihat pada gambar berikut:

DAFTAR PUSTAKA / REFERENSI

Gloor, P. A., Johnson, D. B., Makedon, F., Metaxas, P., (1993), A Visualization System for Correctness Proofs of Graph Algorithms, http://www.wellesley.edu/CS/pmetaxas/visual_proofs.pdf, Computer Science Education, [19 Maret 2010].

Greenberg, H. J., (1998), Greedy Algorithm for Minimum Spanning Tree, http://glossary.computing.society.informs.org/notes/spanningtree.pdf, University of Colorado, Denver, [19 Maret 2010].

Kristanto, A., (2008), Perancangan Sistem Informasi dan Aplikasinya, Gava Media, Yogyakarta.

Mehta, D. P., Sahni, S., (2005), Handbook of Data Structures and Applications, Chapman & Hall/CRC Computer and Information Science Series, United States of America.

Munir, R., (2009), Matematika Diskrit, Edisi 3, Informatika, Bandung.

Oetomo, B. S., (2002), Perencanaan dan Pembangunan Sistem Informasi, Andi, Yogyakarta.

Purbasari, I. Y., (2007), Desain Dan Analisis Algoritma, Edisi 1, Graha Ilmu, Yogyakarta.

Purwanto, E. B., (2008), Perancangan Dan Analisis Algoritma, Edisi 1, Graha Ilmu, Yogyakarta.

Zakaria, T. M., Prijono, A., (2006), Konsep Dan Implementasi Struktur Data, Informatika, Bandung.