Если я правильно понял ваш вопрос, вы хотите получить набор всех ребер, который появляется хотя бы в одном MST.
Очевидно, что время выполнения алгоритма должно быть ограничено снизу в количестве реберв результирующем наборе.
Давайте посмотрим на график Kn (для получения дополнительной информации - https://en.wikipedia.org/wiki/Complete_graph)
На графике O(n^2) ребер, и установите все веса на 1.
Теперь все, что нам нужно, эточтобы доказать, что каждое ребро в этом графе присутствует хотя бы в одном MST, и, таким образом, алгоритм нахождения этого множества должен быть ограничен снизу O(n^2).
Доказательство простое, пусть e = (vi,vj) - ребро, мы можем построитьMST легко связывается с e. Для простоты назовем vi, vj - v1, v2 и, соответственно, все остальные вершины v3, ..., vn. (v1, v2), (v2, v3), ..., (vn-2, vn-1) - это MST.
Итак, в этом случае все ребра находятся вжелаемый набор, и есть O(n^2) ребер, поэтому алгоритм не может выполнить наихудший случай O(nlogn)