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

Question

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

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

Loc1 |  Loc2 |  Distance
  02 |   10  |    2.00 Km
  05 |   07  |    5.39 Km
  02 |   09  |    5.83 Km
  04 |   05  |    5.83 Km
  06 |   08  |    5.83 Km
  03 |   09  |    7.07 Km
  01 |   04  |    11.18 Km
  07 |   09  |    11.18 Km
  07 |   08  |    15.81 Km
Total Weight = 70.12 Km
----------------------------------------------------

Answer 1

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

1. Сориентируйте края так, чтобы результирующая структура имела самый большой родительский узел для каждого узла. Как это сделать? Просто выберите узел и сделайте его корневым. Это дети - узлы первого уровня и т. Д.
2. Теперь сохраните полученный график в формате child-> parent (В вашей таблице вы можете сделать столбец Loc1 дочерним и столбец Loc2 родительским. Индексировать его по дочернему)
3. Для заданных двух узлов a и y, расстояние которых необходимо рассчитать, найдите их родительские множества и посмотрите, где они пересекаются. Ex. Если родителем 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).