Genera número de aristas entre dos nodos
-
29-10-2019 - |
Pregunta
Generé este árbol de expansión mínimo utilizando el algoritmo de Kruskal y me cuesta generar rutas entre dos nodos.¿Alguien puede ayudarme con el pseudocódigo?Intenté usar Lista de adyacencia y matriz de adyacencia
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
----------------------------------------------------
Solución
Si solo desea cualquier ruta entre dos nodos, una Breadth First Search sería suficiente ygeneraría la ruta más corta (porque es un árbol de expansión mínimo).
Otros consejos
Los árboles que abarcan, por definición, no tienen ciclos (o bucles), por lo que a lo sumo, solo puede tener una ruta (es decir, no "rutas", plural) entre dos nodos.
Tal vez no estoy entendiendo la pregunta.¿Estás tratando de encontrar cómo se conectan dos nodos dados en tu árbol?
Si es así, me suena como la fuerza bruta más simple sobre esto, donde solo seguiría de un punto a lo largo de sus posibles bordes, tal vez presionando y estallar las posibilidades de una pila, sería el peor de los casos O (bordes)Tiempo de ejecución, que sería trivial en comparación con el algoritmo de Kruskal. ¿Necesitas algo más rápido?