Comparison of the Prim-Dijkstra and kraskal algorithms on an associative parallel processor

With the help of a model of an associative parallel processor with vertical processing (STAR computer), Prim-Dijkstra and Kraskal algorithms for finding a minimal spanning tree of an undirected graph represented in the form of a list of edges and their weights are compared. A relatively simple representation of the Prim-Dijkstra algorithm is constructed in which the initial node is taken into account. The Kraskal algorithm is also presented and the possibility of eliminating the stage of preliminary sorting of edges by their weights is shown. Translated from Kibernetika i Sistemnyi Analiz, No. 2. pp. 19–27, March–April, 2000.