поддержание сбалансированного остовного дерева растущего неориентированного графа

19

Я ищу способы поддерживать относительно сбалансированное остовное дерево графа, так как я добавляю новые узлы / ребра графа.

У меня есть неориентированный граф, который начинается как один узел, «корень».

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

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

Кто-нибудь знает об онлайн-эвристике, которая будет поддерживать связующее дерево «относительно сбалансированным», в то же время сводя к минимуму объем работы, выполняемой при повторном формировании дерева? У меня есть полный контроль над древовидной структурой. То, что я не контролирую, это связность графа или порядок добавления новых узлов.

Обратите внимание, что стандартные ответы Google на такие термины, как «сбалансированный», «охват» и «дерево», представляются двоичными деревьями и B-деревьями, которые ни к чему не относятся. Мои узлы графа могут иметь любое количество соседей, поэтому узлы дерева могут иметь любое количество дочерних элементов, а не 2, как двоичные деревья. B-деревья поддерживают баланс, изменяя их списки смежности, и я не могу изменить связность графа.

SuperElectric
источник
3
Возможно, было бы полезно, если бы вы были более конкретны в отношении того, каким будет ваше идеальное сбалансированное связующее дерево статического графа. Является ли дерево BFS автоматически хорошим выбором в качестве сбалансированного дерева (оно настолько мелкое, насколько это возможно, если вы выберете правильный корень, или с коэффициентом два независимо от корня)? Вам нужно, чтобы число узлов в каждом поддереве было меньше на постоянный коэффициент, чем количество узлов в родительском элементе, везде в дереве, и если да, что вы делаете для графов, у которых нет таких деревьев?
Дэвид Эппштейн
Дерево BFS действительно было бы идеальным сбалансированным остовным деревом, если бы я работал в автономном режиме, с полным графиком, представленным сразу. Нет необходимости, чтобы число узлов в каждом поддереве было меньше на постоянный коэффициент, чем количество узлов в родительском элементе.
SuperElectric
Вы осматривали топ деревья? en.wikipedia.org/wiki/Top_tree
Peer Sommerlund

Ответы:

4

Каждый раз, когда вы добавляете новую вершину с ребром, у вас нет вариантов. Каждый раз, когда вы добавляете новое ребро, если текущее расстояние до корня больше, чем расстояние через новое ребро, вы удаляете старое ребро в старом кратчайшем пути и добавляете новое. В противном случае вы просто оставите свое дерево без изменений. Я думаю, что таким образом вы получите нечто очень похожее на дерево BFS в том смысле, что уровни дерева будут содержать одинаковые вершины, а расстояние от вершины до корня будет таким же, как расстояние в дереве BFS (и в график), но я не знаю, достаточно ли этого для удовлетворения вашего условия "идеального сбалансированного связующего дерева".

Виниций душ Сантуш
источник
2

Я закончил тем, что сделал следующее:

Ответ Виниция Сантоса - первая его часть. По его словам, в любом кадре я либо добавляю новый узел и ребро-родитель, соединяющее его, либо просто добавляю ребро между двумя существующими узлами. Ребра родитель-потомок не предлагают возможности для изменения древовидной структуры, только ребра. Попробуйте добавить ребро E между узлами A и B, где B имеет большую глубину дерева. Если (A.depth + 1) <B.depth, то мы можем уменьшить B.depth, сделав его потомком A.

Уменьшая глубину B, мы теперь должны проверить соседей B, чтобы увидеть, могут ли они уменьшить свою глубину, став потомками B. Поэтому мы выполняем обход в ширину от B, который пересекает ребро от X до Y, если X. глубина + 1 <Y.depth и устанавливает Y, чтобы быть потомком X.

SuperElectric
источник