Dado un gráfico y dos vértices src y dest, cuente el número total de caminos desde src hasta dest donde la longitud del camino es k (debe haber exactamente k bordes entre ellos). Tenga en cuenta que el gráfico se representa como una array de adyacencia.
Por ejemplo, considere el siguiente gráfico:
El número de caminos del vértice 0 al vértice 3 con longitud 2 es 2 ({0->1->3} y {0->2->3}).
Ya hemos discutido un enfoque O(V 3 K) para contar todas las caminatas posibles desde un origen hasta un destino con exactamente k aristas . En esta publicación, se analiza un enfoque O(V 3 Log K).
Enfoque: La idea es calcular una array resultante donde result = (graph) k . El número total de rutas desde el origen hasta el destino de longitud k será simplemente result[src][dest] . Usamos esta técnica para calcular la exponenciación de la array de adyacencia del gráfico dado.
El árbol recursivo de la función de potencia que se usa aquí para el exponente = 7 se ve a continuación:
A continuación se muestra la implementación del enfoque anterior:
Total number of walks: 2
Complejidad del tiempo:
Publicación traducida automáticamente
Artículo escrito por rituraj_jain y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA