Хотя этот поток слишком старый, у меня есть другой подход для нахождения максимального связующего дерева (MST) в графе G = (V, E)
Мы можем применить некоторый алгоритм Прима для нахождения MST,Для этого я должен определить свойство обрезки для максимального взвешенного края.
Свойство обрезки: допустим, в любой точке у нас есть набор S, который содержит вершины в MST (на данный момент предположим, что он каким-то образом рассчитывается),Теперь рассмотрим набор S / V (вершины не в MST):
Заявка: ребро от S до S / V, имеющее максимальный вес, всегда будет в каждом MST.
Доказательство:Скажем, в момент, когда мы добавляем вершины к нашему множеству S, максимальный взвешенный край от S до S / V равен e = (u, v), где u находится в S, а v находится в S / V.Теперь рассмотрим MST, который не содержит e.Добавьте ребро e в MST.Это создаст цикл в оригинальном MST.Пройдите через цикл и найдите вершины u 'в S и v' в S / V так, чтобы u 'была последней вершиной в S, после чего мы вводим S / V, а v' - первая вершина в S / V на пути вцикл от u до v.
Удалите ребро e '= (u', v '), и результирующий граф все еще подключен, но вес e больше, чем e' [так как e - максимальное взвешенное реброот S до S / V в этой точке], так что это приводит к MST, у которого сумма весов больше, чем у исходного MST.Так что это противоречие.Это означает, что ребро e должно быть в каждом MST.
Алгоритм нахождения MST:
Start from S={s} //s is the start vertex
while S does not contain all vertices
do
{
for each vertex s in S
add a vertex v from S/V such that weight of edge e=(s,v) is maximum
}
end while
Реализация: мы можем реализовать, используя Max Heap / Priority Queue, где ключ - это максимальный весребро от вершины в S до вершины в S / V и значением является сама вершина.Добавление вершины в S равно Extract_Max из кучи, и при каждом Extract_Max меняйте ключ вершин, смежных с только что добавленной вершиной.
Таким образом, требуется m операций Change_Key и n операций Extract_Max.
Extract_Min и Change_Key оба могут быть реализованы в O (log n).n - количество вершин.
Так что это занимает O (m log n) времени.m - количество ребер в графе.