Ruta de longitud fija entre dos nodos gráficos

Question

¿Hay un algoritmo que, si se le dan dos nodos en un gráfico, encuentre una ruta entre ellos que tome el número especificado de saltos? Cualquier nodo se puede conectar a cualquier otro.

Los puntos en este momento están ubicados en el espacio 2D, por lo que no estoy seguro de que una gráfica sea la mejor opción.

Answer 1

Si tiene nodos que buscan encontrar rutas en términos de saltos, entonces una gráfica es probablemente el enfoque correcto. Sin embargo, no estoy seguro de entender lo que intenta hacer y cuáles son las restricciones, especialmente con respecto a " Cualquier nodo puede conectarse a cualquier otro " .. que parece un poco abierto terminado.

Sin embargo, sin tener en cuenta eso; con alguna representación gráfica:

Parece que comienza en el primer nodo y realiza una primera búsqueda en profundidad desde allí, y termina una búsqueda si (a) los saltos realizados son mayores que su número especificado o (b) hemos llegado al segundo nodo; esto determinará la primera (no solo) ruta que conecta los dos nodos en (como máximo) esa cantidad de saltos.

Si tiene que ser exactamente los saltos especificados, finalice cualquier rama de la búsqueda si los saltos se han superado y finalice con éxito si también ha llegado al segundo nodo.

Answer 2

¿Has probado DFS iterativo y profundo ?

Answer 3

Enfoque tonto: (la estructura de datos es una matriz de pilas). Básicamente, esto está haciendo Breadth First Search (BFS) hasta la profundidad N, excepto que si los bucles están permitidos (no aclaró pero supongo que sí), no excluye los nodos visitados de una mayor búsqueda.

1. Empuje el nodo de inicio en una pila almacenada en la matriz en el índice 0 (índice = profundidad)

2. Para cada nivel / índice " l " 0-N:

   Para cada nodo en una pila almacenada en el nivel '' l '', encuentre todos sus vecinos y empújelos en una pila almacenada en el nivel '' l + 1 ''.

   Importante: si su tarea permite encontrar rutas que contienen bucles, NO verifique si ya visitó algún nodo que agregue. Si no permite bucles, use un hash de nodos visitados para no agregar ningún nodo dos veces **

3. Deténgase cuando termine el nivel " N-1 " ;.

4. Recorre todos los nodos que acabas de agregar para apilar en el índice " N " y encuentra tu nodo de destino. Si se encuentra: éxito, si no, no existe tal ruta.

Tenga en cuenta que si por " todos los nodos se pueden conectar " Usted está implicando un gráfico COMPLETAMENTE CONECTADO, entonces existe una respuesta matemática que no implica la visita de nodos

(sin embargo, la fórmula es demasiado larga para escribir en el campo de entrada de texto de StackOverflow)