Час роботи алгоритму Краскала з деревовидною та списковою структурою даних

• Main Authors: Trofimchuk, A. N., Vasyanin, V. A.
• Format: Article
• Language: rus
• Published: The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2015
• Online Access: http://journal.iasa.kpi.ua/article/view/53409

Using numerical experiments, two implementations of Kruskal's algorithm based on the linked lists (the proposed algorithm) and tree (Tarjan's algorithm) data structures were compared with Prim's algorithm. The comparison results allow to claim that for practical problems of finding the minimum or maximum spanning trees (forest), the algorithms with linked lists data structure work no worse, and, in most cases, faster, than algorithms with the tree data structure. A practical assessment of complexity of the proposed algorithm for a connected graph was shown O(e), where e — the number of edges of the graph. It was experimentally proved that algorithm’s running time on connected sparse graphs was comparable to the time of sorting the edges of a graph by a bucket sort method. The proposed algorithm works faster than Prim's algorithm for graphs with the number of edges no more, than 0,27e2, where v is the number of vertices of the graph. The pilot study of the algorithm on the graphs containing between 499500 and 71994000 edges, showed its high computing efficiency; therefore, it can be recommended for solving practical problems on sparse graphs or networks of a big size.