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

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

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

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
----------------------------------------------------

algorithm graph-algorithm depth-first-search minimum-spanning-tree kruskals-algorithm
person Santhosh    schedule 21.02.2012    source источник
comment
Он уже есть на твоем столике, не так ли?   -  person ElKamina    schedule 21.02.2012
comment
@ElKamina .. Я хочу программно хранить все пути в списке или массиве, чтобы я мог рассчитать количество переходов. Например, из приведенного выше MST, как мне рассчитать количество переходов между Loc 1 и Loc 3   -  person Santhosh    schedule 21.02.2012

Ответы (1)


arrow_upward
2
arrow_downward

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

  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).

person ElKamina    schedule 21.02.2012