Сохранение информации о пути в алгоритме Крускала

Question

Я сгенерировал минимальное остовное дерево с помощью алгоритма Крускала и хотел знать, как хранить пути

Это мое минимальное остовное дерево

родовое слово

Answer 1

Это зависит от того, сколько у вас свободного места. Предположим, вам нужно экономить пространство:

1. Сориентируйте края так, чтобы полученная структура максимум один родительский узел для каждого узла. Как это сделать? Просто выберите узел и сделайте его корнем. Его дочерние элементы - это узлы первого уровня и т. Д.
2. Теперь сохраните получившийся график в формате дочерний-> родительский (в своей таблице вы можете сделать столбец Loc1 дочерним, а столбец Loc2 родительским. Индексируйте его по дочернему элементу)
3. Для данных двух узлов, a и y, расстояние до которых необходимо вычислить, найдите их родительские наборы и посмотрите, где они пересекаются. Бывший. Если родительский элемент x - A, родительский элемент A - B ... родительский путь - ABCDLMN (где N - корень). Аналогично, если родительский корень для y - EFLMN. Как видите, наименьший общий корень для них обоих равен L. Расстояние от x-> L равно 5, y-> L равно 3,=> расстояние между x и y равно 5 + 3= 8.

Сложность: O (hlogn), где h - высота дерева, а n - количество элементов в дереве (я предполагаю время поиска для каждого узла в logn).