График минимального связующего дерева с использованием BFS

Question

Это проблема практического экзамена, с которой я борюсь:

Пусть G = (V, E) - взвешенный неориентированный связный граф с положительными весами (вы можете предположить, чтовеса различны).Для вещественного числа r определим подграф Gr = (V, {e в E | w (e) <= r}).Например, у G0 нет ребер (очевидно, несвязных), а Ginfinity = G (который по условию связан).Проблема состоит в том, чтобы найти наименьшее значение r, такое, что Gr связан. </p>

Опишите алгоритм времени O (mlogn), который решает проблему путем многократного применения BFS или DFS.

Настоящая проблема заключается в том, чтобы сделать это в O (mlogn).Вот что у меня есть:

r = min( w(e) )                            => O(m)
while true do                              => O(m) 
  Gr = G with edges e | w(e) > r removed     => O(m)
  if | BFS( Gr ).V | < |V|                   => O(m + n)
    r++ (or r = next smallest w(e))          
  else
    return r

Это колоссальный O (m ^ 2 + mn).Какие-нибудь идеи для того, чтобы получить это к O (mlogn)?Спасибо!

Answer 1

Вы перебираете все возможные граничные затраты, что приводит к внешнему циклу O (m). Обратите внимание, что если график отключен, когда вы отбрасываете все ребра> w (e), он также отключается для> w (e '), где w(e') < w(e). Вы можете использовать это свойство, чтобы выполнить бинарный поиск по граничным затратам и, таким образом, сделать это в O (log (n)).

lo=min(w(e) for e in edges), hi=max(w(e) for e in edges)
while lo<hi:
   mid=(lo+hi)/2
   if connected(graph after discarding all e where w(e)>w(mid)):
       lo=mid
   else:
       hi=mid-1
return lo

Бинарный поиск имеет сложность O (log (max_e-min_e)) (вы можете фактически уменьшить его до O (log (ребра)), и отбрасывание ребер и определение связности может быть сделано в O (ребра + вершины) , так что это можно сделать в O ((ребро + вершины) * log (ребра)).

Предупреждение: я еще не проверял это в коде, поэтому могут быть ошибки. Но идея должна работать.

Answer 2

Как насчет следующего алгоритма?

Сначала возьмите список всех ребер (или всех различных длин ребер, используя) из графика и отсортируйте их. Для этого требуется время O (m * log m) = O (m * log n): обычно m меньше n ^ 2, поэтому O (log m) = O (log n ^ 2) = O (2 * log n) = O (log n).

Очевидно, что r должно быть равно весу некоторого ребра. Таким образом, вы можете выполнить бинарный поиск по индексу ребра в отсортированном массиве.

Для каждого индекса, который вы пытаетесь, вы берете длину соответствующего ребра в качестве r и проверяете граф на связность, используя только ребра длины <= r с BFS или DFS. </p>

Каждая итерация двоичного поиска занимает O (m), и вы должны сделать O (log m) = O (log n) итераций.