La cuestión es que lo que está haciendo es correcto con respecto al tiempo ineficiente. Un bfs de un gráfico con vértices V y aristas E toma O (V + E) si está utilizando una lista de adyacencia. Entonces, si haces bfs para cada vértice, la complejidad general se convertiría en O (V * (V + E)). Por otro lado, si lo hace utilizando 2 BFS / 2 DFS, la complejidad temporal sería O (2 * (V + E)), que no es más que O (V + E), que es muy inferior en comparación con eso en tu enfoque. Por eso, en todos los lugares de Internet, se analiza el método que usa 2 dfs / 2bfs.
Cómo lo hice fue usar 2 DFS. Aquí está mi enfoque
- Comience desde el primer nodo, diga S. (aunque puede comenzar desde cualquier nodo)
- Haz un dfs del árbol a partir de S. Durante el dfs, almacene las distancias de cada nodo desde S en una matriz, por ejemplo dp1 [] sea esta matriz. (Asegúrese de que los índices de esta matriz sean los mismos que los números de vértice (números de nodo) del gráfico).
- Encuentre el índice del valor máximo de esta matriz dp1 [] y almacénelo en una variable, digamos maxx.
- Haga un dfs del árbol comenzando desde el nodo con número == maxx. Durante este dfs, almacene las distancias de cada nodo desde maxx en una matriz, por ejemplo dp2 []. (Asegúrese de que los índices de esta matriz sean los mismos que los números de vértice (números de nodo) del gráfico).
- El máximo de los valores almacenados en dp2 [] es la ruta más larga entre dos nodos en el árbol. Salida de este valor máximo.
Aquí está el código de trabajo que envié: AarushJ / acm-icpc-practice
- ¿Cuál sería la mejor manera de integrar el algoritmo de aprendizaje para clasificar en Solr?
- ¿Qué algoritmo de búsqueda aplicaría para la siguiente matriz y por qué?
- ¿Por qué deberíamos conocer más de un algoritmo de clasificación en Python (burbuja, inserción, selección) si todos están haciendo el mismo trabajo?
- ¿Qué hace que NP-hard sea más difícil?
- ¿Cómo se siente Bram Cohen al haber creado accidentalmente un algoritmo para el cifrado totalmente homomórfico?
