Я ищу способы поддерживать относительно сбалансированное остовное дерево графа, так как я добавляю новые узлы / ребра графа.
У меня есть неориентированный граф, который начинается как один узел, «корень».
На каждом шаге я добавляю к графу либо новый узел и ребро, соединяющее его с графом, либо просто новое ребро, соединяющее два старых узла. По мере роста графика я поддерживаю связующее дерево. В большинстве случаев это означает, что когда я добавляю новый узел и ребро, я устанавливаю новый узел как дочерний узел старого узла, к которому он подключается.
У меня нет контроля над порядком, в котором добавляются новые узлы, поэтому приведенный выше алгоритм построения дерева может привести к несбалансированным связующим деревьям.
Кто-нибудь знает об онлайн-эвристике, которая будет поддерживать связующее дерево «относительно сбалансированным», в то же время сводя к минимуму объем работы, выполняемой при повторном формировании дерева? У меня есть полный контроль над древовидной структурой. То, что я не контролирую, это связность графа или порядок добавления новых узлов.
Обратите внимание, что стандартные ответы Google на такие термины, как «сбалансированный», «охват» и «дерево», представляются двоичными деревьями и B-деревьями, которые ни к чему не относятся. Мои узлы графа могут иметь любое количество соседей, поэтому узлы дерева могут иметь любое количество дочерних элементов, а не 2, как двоичные деревья. B-деревья поддерживают баланс, изменяя их списки смежности, и я не могу изменить связность графа.
источник
Ответы:
Каждый раз, когда вы добавляете новую вершину с ребром, у вас нет вариантов. Каждый раз, когда вы добавляете новое ребро, если текущее расстояние до корня больше, чем расстояние через новое ребро, вы удаляете старое ребро в старом кратчайшем пути и добавляете новое. В противном случае вы просто оставите свое дерево без изменений. Я думаю, что таким образом вы получите нечто очень похожее на дерево BFS в том смысле, что уровни дерева будут содержать одинаковые вершины, а расстояние от вершины до корня будет таким же, как расстояние в дереве BFS (и в график), но я не знаю, достаточно ли этого для удовлетворения вашего условия "идеального сбалансированного связующего дерева".
источник
Я закончил тем, что сделал следующее:
Ответ Виниция Сантоса - первая его часть. По его словам, в любом кадре я либо добавляю новый узел и ребро-родитель, соединяющее его, либо просто добавляю ребро между двумя существующими узлами. Ребра родитель-потомок не предлагают возможности для изменения древовидной структуры, только ребра. Попробуйте добавить ребро E между узлами A и B, где B имеет большую глубину дерева. Если (A.depth + 1) <B.depth, то мы можем уменьшить B.depth, сделав его потомком A.
Уменьшая глубину B, мы теперь должны проверить соседей B, чтобы увидеть, могут ли они уменьшить свою глубину, став потомками B. Поэтому мы выполняем обход в ширину от B, который пересекает ребро от X до Y, если X. глубина + 1 <Y.depth и устанавливает Y, чтобы быть потомком X.
источник