Almacenamiento de información de ruta en el algoritmo de Kruskal

Question

He generado un árbol de expansión mínimo utilizando el algoritmo de Kruskal y quería saber cómo almacenar rutas

Este es mi árbol de expansión mínimo

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

Depende de la cantidad de espacio adicional que tenga. Suponga que necesita ahorrar espacio:

1. Oriente los bordes de tal manera que la estructura resultante tenga la mayoría de un nodo padre para cada nodo. ¿Cómo hacerlo? Simplemente elija un nodo y conviértalo en la raíz. Sus hijos son nodos de primer nivel, etc.
2. Ahora almacene el gráfico resultante en el formato child-> parent (en su tabla puede hacer que la columna Loc1 sea secundaria y la columna Loc2 sea la principal. Indexe por hijo)
3. Para dos nodos dados, ay, cuya distancia necesita calcularse, busque sus conjuntos parentales y vea dónde se cruzan. Ex. Si el padre de x es A, el padre de A es B ... la ruta de los padres es ABCDLMN (donde N es la raíz). Del mismo modo, si la raíz parental de y es EFLMN. Como puede ver, la raíz común más baja para ambos es L. La distancia desde x-> L es 5, y-> L es 3,=> la distancia entre xey es 5 + 3= 8.

Complejidad: O (hlogn) donde h es la altura del árbol yn es el número de elementos en el árbol (supongo que el tiempo de búsqueda para cada nodo en el registro).