Пространственное минимальное связующее дерево

Question

Я столкнулся с задачей, которая в основном просит вас найти MST данного графа, в котором все вершины связаны.Я попытался использовать алгоритм Крускала, но вскоре понял, что граница пространства слишком тесная, чтобы можно было хранить все ребра в мегибайтах, поэтому я также отказался от алгоритма Прима и Борувки.Есть ли способ реализовать какой-либо из этих алгоритмов (или любой другой алгоритм MST) с пространственной сложностью лучше, чем O (E), которая в этом случае O (V ^ 2)?

Answer 1

Для случая, когда вы можете вычислить веса, используя функцию w (i, j), вы можете вычислить минимальное остовное дерево в пространстве O (n) вместо O (n ^ 2), используя алгоритм Прима (https://en.wikipedia.org/wiki/Minimum_spanning_tree#Classic_algorithms).

На каждом этапе поддерживать набор T узлов в дереве, а для каждого узла, не входящего в дерево, поддерживать наименьшее расстояние от этого узла до любого узла в дереве.

В начале Tэто узел 0, и для каждого другого узла вы вычисляете наименьшее расстояние от узла 0 до этого узла.

На каждом этапе выберите узел, не входящий в дерево с наименьшим расстоянием. Теперь вычислите расстояние от этого узла до всех остальныхузлы не в дереве. Если это меньше, чем их текущее наименьшее расстояние, обновите это наименьшее расстояние.

Стоимость хранения составляет O (n) для поддержания T и O (n) для поддержания для каждого узла, не входящего в деревопримечание о наименьшем расстоянии от дерева до этого узла.