Résumé
The minimum spanning tree (MST) is a widely used method in the study of networks. There have been substantial contributions to derive algorithms to find the MST from a set of pairwise distances. The MST may not be unique for a given data set because of the presence of ties in the distances. There seems to be no efficient implementation able to enumerate or list all MSTs compatible with a given data set. This contribution attempts to fill this gap. The approach adopted here makes use of the Laplacian minors of the distance matrix combined with some efficient code to compute matrix determinants. Two algorithms are presented: the first one builds a network that contains all MSTs compatible with the distances given as input; the second one counts the number of alternative MSTs during the aggregation process of the first one. Analyses of the TSPLIB benchmark data made of 111 sets sizes (with up to $ n\,=\,85,900 $ nodes) showed that running times practically scaled with $ n<^>{1.96} $. This is very close to the expected time complexity of the well-known Kruskal algorithm ($ \approx n<^>{2} $) showing that the proposed algorithms are expected to run in polynomial time. Computer code is provided in a public repository to implement the algorithms.