Time complexity of Kruskal's algorithm with tree and linked list data structures
Abstract
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.References
Boruvka O. O jistém problému minimálním // Pràca Moravské Prirodovedecké Spolecnosti. – 1926. – 3. – P. 37–58.
Nešetřil J.E., Milková H., Nešetřilová. Otakar Borůvka on minimum spanning tree problem: translation of both the 1926 papers, comments, history // Discrete Mathematics. – 2001. – 233 (1–3). – P. 3–36.
Jarník V. O jistém problému minimálním // Práce Moravské Prirodovedecké Spolecnosti. – 1930. – 6. – P. 57–63.
Prim R.C. Shortest Connection Networks and Some Generalizations // Bell Syst. Tech. J. – 1957. – 36. – P. 1389–1401.
Dijkstra E. A note on two problems in connexion with graphs // Num. Math. – 1959. – 1. – P. 269–271.
Kruskal J.B. On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem // Proc. Amer. Math. Soc. – 1965. – 7. – P. 48–50.
Loberman H., Weinberger A. Formal procedures for connecting terminals with a minimum total wire length // Journal of ACM. – 1957. – 4. – P. 428–437.
Sollin M. Le tracé de canalisation // Programming, Games, and Transportation Networks (in French). – 1965.
Tarjan R.E. Data Structures and Network Algorithms. – Philadelphia: Society for Industrial and Applied Mathematics, 1983.
Graham R.L., Hell P. On the History of the Minimum Spanning Tree Problem // Annals of the History of Computing. – 1985. – 7(l). – P. 43–57.
Knut D. Iskusstvo programmirovaniya dlya EVM. T.3 (Sortirovka i poisk). – M.: Mir, 1978. – 800 s.
Ahuja R.K., Orlin J.B., Magnanti T.L. Network flows: theory, algorithms, and applications. – New Jersey: Prentice-Hail, Inc. Upper Saddle River, 1993. – 846 p.
Аkho А., Dzh. KHopkhroft, Dzh. Ul’man. Struktury dannykh i algoritmy: Per. s angl.: Uch. pos. – M.: Izdatel’skiy dom "Vil’yame", 2000. – 384 s.
Sedzhvik R. Fundamental’nyye algoritmy na C . Аlgoritmy na grafakh: Per. s angl. – SPb: OOO "DiaSoftYUP", 2002. – 496 s.
Kormen T., Leyzerson CH., Rivest R., SHtayn K. Аlgoritmy: postroyeniye i analiz, 2-e izdaniye: Per. s angl. – M.: Izdatel’skiy dom "Vil’yams", 2005. – 1296 s.
Mehlhorn K., Sanders P. Algorithms and Data Structures. The Basic Toolbox. – Springer-Verlag Berlin Heidelberg, 2008. – 305 p.
Boost.org. Boost C++ Libraries. – www.boost.org.
LEDA (Library of Efficient Data Types and Algorithms). – www.algorithmicsolutions.com.
Goodrich M.T., Tamassia R. JDSL – the data structures library in Java. – http://www.jdsl.org/.
Vasyanin V.А. O vychislitel’noy effektivnosti odnogo algoritma dlya nakhozhdeniya osnovnogo lesa grafa s minimal’nym (maksimal’nym) vesom // Ekolohichna bezpeka ta pryrodokorystuvannya: Zb. nauk. prats'. – Kyyiv, 2009. – Vyp. 4. – S. 155–169.
Tarjan R.E. Efficiency of a good but not linear set union algorithm // Journal of the ACM. – 1975. – 22, № 2. – P. 215–225.
Gabow H.N., Galil Z., Spencer T., Tarian R.E. Efficient algorithms for finding minimum spanning trees in undirected and directed graphs // Combinatorica. – 1986. – 6. – P. 109–122.
Chazelle B. The Soft Heap: An Approximate Priority Queue with Optimal Error Rate // Journal of the ACM. – 2000. – 47. – P. 1012–1027.
Chazelle B. A minimum spanning tree algorithm with inverse-Ackermann type complexity // Journal of the ACM. – 2000. – 47. – P. 1028–1047.
Pettie S., Ramachandran V. An optimal minimum spanning tree algorithm // In 7th International Colloquium on Automata, Languages and Programming: of Lecture Notes in Computer Science, Springer, 2000. – 1853. – P. 49–60.
Pettie S., Ramachandran V. Randomized minimum spanning tree algorithms using exponentially fewer random bits // ACM Transactions on Algorithms. – 2008. – 4, № 1. – P. 1–27.
Tarjan R.E., Leeuwen J.V. Worst-Case Analysis of Set Union Algorithms // J. of the ACM. – 1984. – 31, № 2. – P. 245–281.
Tarjan R.E. Amortized computational complexity // SIAM J. on Algebraic and Discrete Methods. – 1985. – 6, № 2. – P. 306–318.
