PENERAPAN TEORI GRAF UNTUK MENYELESAIKAN MASALAH MINIMUM SPANNING TREE (MST) MENGGUNAKAN ALGORITMA KRUSKAL

Swaditya Rizki(1*),

(1) Universitas Muhammadiyah Metro
(*) Corresponding Author


Abstract


One of useful graph theory to solve the real problems is Minimum Spanning Tree (MST). MST is network optimization problems that can be applied in many fields such as transportations problems and communication network design (Gruber and Raidl, 2005). MST begins from tree namely a connected graph has no circuits. From the graph, there is a sub-graph that has all the vertex or spanning tree. If that graph has the weight/cost, then the spanning tree that has the smallest weight/cost is called Minimum Spanning Tree. Basic algorithm used to determine the MST is Kruskal’s algorithm. This algorithm is known as one of the best algorithms for the optimization problems, especially for MST. In this paper is developed a source code program to determine MST using Kruskal’s algorithm and then implemented on several data representing a complete graph.

Full Text:

PDF

References


Deo, N. 1989. Graph Theory with Applications to Engineering and Computer Science. Prentice Hall, Inc. Englewood Cliffs, New Jersey. 461 hlm.

Gruber, M. and Raidl, G.R. 2005. Variable Neighborhood Search for the Bounded Diameter Minimum Spanning Tree Problem. Institute of Computer Graphics and Algorithms, Vienna University of Technology. 18th Mini Euro Conference . Austria.

Munir, R. 2001. Matematika Diskrit. Informatika, Bandung. Hlm 353-456.

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition., 2001. ISBN 0-262-03293-7. Section 23.2: The algorithms of Kruskal and Prim, pp.567–574. MIT Press and McGraw-Hill.




DOI: http://dx.doi.org/10.24127/ajpm.v1i2.68

Refbacks

  • There are currently no refbacks.