Частный случай алгоритма MST за линейное время

Пусть G = (V, E) - взвешенный неориентированный связный граф, в котором веса всех ребер различны. Пусть T обозначает минимальное остовное дерево.

Предположим, что G имеет m ≤ n + 157 ребер. Для этого особого случая дайте алгоритм MST, который работает за O (n) раз, опережая алгоритм Краскала и Примса.

Какие-нибудь намеки?


algorithm prims-algorithm kruskals-algorithm
person Tom Qiu    schedule 20.03.2018    source источник
comment
Вы можете отсортировать края за O (n) и продолжить работу с алгоритмом Краскала.   -  person Nico Schertler    schedule 20.03.2018

Ответы (1)


arrow_upward
0
arrow_downward

Сначала убедитесь, что граф связан.

Затем повторяйте, пока граф не станет деревом (# ребер = n-1):

  • Найдите цикл с помощью DFS. Должен быть один, поскольку #edges> = n
  • Удалите самый длинный край в цикле. Он не может быть частью MST.

Когда закончите, вы останетесь с MST.

Несмотря на то, что это может занять O (n) раз на итерацию, будет не более 158 итераций, так что все вместе это O (n).

person Matt Timmermans    schedule 20.03.2018