20.500.12556/RUL-176570 Computing well-balanced spanning trees of unweighted networks A spanning tree of a network or graph is a subgraph that connects all nodes with the minimum number or total weight of edges. Spanning trees are among the simplest yet most effective techniques for network simplification, sampling, and uncovering a network’s backbone or skeleton. Prim’s algorithm and Kruskal’s algorithm are well-known algorithms for computing a spanning tree of a weighted network, and are therefore also the default procedure for unweighted networks in the most popular network libraries. In this paper, we empirically evaluate the performance of these algorithms on unweighted networks and compare them with priority-first search algorithms. We show that the distances between the nodes are better preserved by a simpler algorithm based on breadth-first search. The spanning trees are also more compact and well-balanced, as measured by classical graph indices. We support our findings with experiments on synthetic graphs and over a thousand real networks, and demonstrate the practical applications of the computed spanning trees. We conclude that for preserving the structure of an unweighted network, the breadth-first search algorithm should be the preferred choice. unweighted networks spanning tree breadth-first search Prim’s algorithm Kruskal’s algorithm neutežena omrežja vpeto drevo preiskovanje v širino Primov algoritem Kruskalov algoritem true false true Angleški jezik Slovenski jezik Članek v reviji 2025-12-04 09:38:08 2025-12-04 09:38:09 2025-12-22 04:06:05 0000-00-00 00:00:00 2025 0 0 18 str. iss. 12, art. 760 Vol. 18 Dec. 2015 0000-00-00 Zaloznikova Objavljeno apc 0000-00-00 0000-00-00 0000-00-00 004.021 1999-4893 10.3390/a18120760 259877379 RAZ_Subelj_Lovro_2025.pdf RAZ_Subelj_Lovro_2025.pdf 1 C2874BFC6635EB9061E994F8E811271E 6b7926f8158fc17dccec115a7bf3e5d5881f215f31f8962f0f42d5b25f03e72f 9e46cb7e-d0ec-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=222981 https://www.mdpi.com/1999-4893/18/12/760 1 2c8037ca-d0ec-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=222980 Fakulteta za računalništvo in informatiko 0 0 0