Gracias a todos los que respondieron con ideas y soluciones alternativas. Las formas más eficientes de resolver problemas siempre son bienvenidas, así como recordatorios para cuestionar mis suposiciones. Dicho esto, me gustaría que ignoraras por un momento el problema que estoy tratando de resolver con el algoritmo, y que me ayudes a analizar la gran complejidad de mi algoritmo tal como lo he escrito, y es todo un camino simple. en un gráfico que utiliza la búsqueda de profundidad limitada como se describeaquí, e implementadoaquí. ¡Gracias!

Edición: esta es la tarea, pero ya he enviado esta tarea y me gustaría saber si mi respuesta es correcta. Me confundo un poco sobre la complejidad de Big-O cuando se trata de recursión.

Pregunta original a continuación:

Estoy tratando de encontrar la complejidad de una búsqueda de todos los caminos como lo indicaesta algoritmo. Dados dos vértices, estoy encontrando todos los caminos simples entre ellos usando una búsqueda en profundidad.

Sé que la complejidad temporal de DFS es O (V + E) y su complejidad de espacio es O (V), y mi intuición es que la complejidad de una búsqueda de todos los caminos será más que eso, pero no puedo determina lo que será.

Preguntas de SO relacionadasaquí yaquí.

Actualización (en respuesta a un comentario a continuación):

Estoy tratando de resolver elseis grados de Kevin Bacon problema. Esto generalmente requiere encontrar el grado más bajo de separación entre un par de actores, pero tengo que encontrar TODOS los grados de separación (por ahora, menos de 6, pero esto puede cambiar).