SIMULASI MINIMUM SPANNING TREE GRAF BERBOBOT MENGGUNAKAN ALGORITMA PRIM DAN ALGORITMA KRUSKAL

Abstract

There are so many problems that can be encountered by graphtechnique,  especially in the realm of information technology (IT). One of the problems is to compute aMinimum Spanning Tree (MST). By using this kind of technique, it will be obtained a range of connected lines with its merits; e.g., the  spanning tree  of minimum cost, the  least weight, and so on. There are  commonly two algorithms to find minimum spanning tree  (MST) namely Prim’s algorithm and Kruskal’s algorithm. This research aims to examine whether  or not Prim’s algorithm and Kruskal’s algorithm can be used to calculate minimum spanning tree (MST) of a connected weighted graph, to know more about the approximate time to compute minimum spanning tree (MST) of a connected weighted graph through the implementation  of Prim’s algorithm and Kruskal’s algorithm, and to find out which one of these two algorithms work best to calculate minimum spanning tree (MST) of a connected weighted graph. The development  of software  application in calculating MST using Prim’s algorithm and Kruskal’s algorithm is operated  by Windows 7, the so-called Free Pascal Program, which includes the steps of observing  and  data  gathering,  the  installation of the  program,  designing graph  model that  the weights are in accordance with the data gathered  by Free Pascal Program, simulating the model of MST weighted graph through Prim’s algorithm and Kruskal’s algorithm by using Free Pascal Program to calculate the longest edge, the order of MST, computation  time, and, lastly, to test and conclude the test result.  The data simulation uses the data of PDAM pipeline “PerumnasPatrangJember”.  The result shows that MST program used perfectly proved that Prim’s algorithm and Kruskal’s algorithm can be implemented to calculate the minimum spanning tree (MST) of a connected weighted graph. The MST program usedcan also simulate and calculate the length of the MST weighted graph through the  implementation  of Prim’s algorithm and Kruskal’s algorithm.Based on the  test  result, the  run time of Kruskal’s algorithm is shorter and/or  faster than the Prim’s algorithm to calculate a various MST weighted graph.

Keywords: Simulation, Minimum Spanning  Tree (MST), Prim’s algorithm, Kruskal’s algorithm, Free Pascal