Me gustaría encontrar una ruta de longitud fija (dada durante la ejecución del programa) en un gráfico no dirigido. Estoy usando la matriz de adyacencia de mi gráfica.
Intenté usar algunos algoritmos como DFS o A *, pero solo devuelven la ruta más corta.

Los nodos no pueden ser visitados de nuevo.

Así que digamos que mi gráfica tiene 9 nodos y la ruta más corta se construye a partir de 4 nodos.
Quiero tener una variable adicional que "diga" el algoritmo que quiero encontrar la ruta que tiene 7 nodos (por ejemplo) y devolverá los nodos que están incluidos en mi ruta esperada {1,2,4,5,6, 7,8}.
Por supuesto, si no hay una solución para la ruta que deseo, no devolverá nada (o devolverá la ruta cerca de mis expectativas, digamos 19 en lugar de 20).

Alguien dijo sobre el DFS con retroceso, pero no sé nada al respecto.
¿Podría alguien explicar cómo usar DFS con retroceso o recomendar algunos otros algoritmos para resolver ese problema?