Eu gostaria de encontrar o caminho de comprimento fixo (dado durante a execução do programa) no gráfico não direcionado. Eu estou usando a matriz de adjacência do meu gráfico.
Eu tentei usar alguns algoritmos como DFS ou A *, mas eles só retornam o caminho mais curto.

Os nós não podem ser visitados novamente.

Então, digamos que meu gráfico tenha 9 nós e que o caminho mais curto seja construído a partir de 4 nós.
Eu quero ter uma variável adicional que irá "dizer" o algoritmo que eu quero encontrar o caminho que tem 7 nós (por exemplo) e ele irá retornar nós que estão incluídos no meu caminho esperado {1,2,4,5,6, 7,8}.
É claro que, se não houver solução para o caminho que eu quero, ele não retornará nada (ou retornará o caminho próximo às minhas explicações, digamos 19 em vez de 20).

Alguém disse sobre o DFS com backtracking, mas eu não sei nada sobre isso.
Alguém poderia explicar como usar o DFS com backtracking ou recomendar alguns outros algoritmos para resolver esse problema?