1 Begin with a connected graph G containing edges of distinct weights, and an empty set of edges T
2 While the vertices of G connected by T are disjoint:
3 Begin with an empty set of edges E
4 For each component:
5 Begin with an empty set of edges S
6 For each vertex in the component:
7 Add the cheapest edge from the vertex in the component to another vertex in a disjoint component to S
8 Add the cheapest edge in S to E
9 Add the resulting set of edges E to T.
10 The resulting set of edges T is the minimum spanning tree of G.
Из Википедии.Я понимаю, что внешний цикл - это logV, так как вы присоединяетесь к множествам.Но затем следует внутренний цикл.
Если вы используете отношения эквивалентности для отслеживания наборов, это означает, что вы получаете только элемент, представляющий набор, поэтому вы не можете определить ребро с наименьшим весоммежду двумя наборами, потому что у вас нет всех элементов.Если вы измените структуру так, чтобы она содержала ссылки на дочерние элементы, вам все равно придется получить все дочерние элементы каждого набора.Это означает, что в худшем случае O (V / 2) = O (V) для каждого набора.
После этого вам все еще нужно найти наименьшее ребро, соединяющее два, что означает пересечение всех ребер, соединяющих два компонента.Поэтому вам нужно перебрать каждый узел и посмотреть, соединяется ли его ребро с элементом в другом компоненте, и если да, то если оно меньше минимального ребра, которое у вас есть в данный момент.итерация по узлам и внутреннему циклу для итерации по краям этих узлов - O (V E).Поскольку он находится внутри цикла O (logV), вы получаете O (logV V * E).
Теперь кажется, что вам просто нужно перебрать все ребра, но как бы вы выбралиминимальный край между двумя компонентами?Я могу сказать, соединяет ли данное ребро узлы в разных компонентах, но я не могу сказать, какой из них соединяет их, имеет минимальный вес.И если я получу тот, у которого минимальный вес, он может их не соединить.