En general, se sabe que el problema del isomorfismo gráfico es NP-completo. Si el gráfico es un árbol, existe un algoritmo de tiempo polinómico que usa hashing (puede leer más sobre esto aquí).
La solución de hash se usa porque, dado que un nodo en el primer árbol que sabemos es equivalente a algún nodo particular en el segundo árbol, no sabemos qué hijo del primer nodo es isormórfico para cada hijo del segundo. Por lo tanto, tomamos los hashes.
Pero dado que especifica que los árboles son árboles de búsqueda binarios, la solución se vuelve mucho más simple. El orden de los niños ya está decidido. Entonces, el hijo izquierdo del primer nodo TIENE que ser isomorfo al hijo izquierdo del segundo nodo. Y similar en el caso de los niños correctos. Entonces, obtienes un algoritmo de tiempo lineal simple O (V + E) .
- Cómo encontrar los cambios mínimos necesarios para convertir una cuerda en un palíndromo
- ¿Hay algún buen sitio para aprender algoritmos / conceptos de programación todos los días (similar a la pregunta SAT del día)?
- ¿Dónde y cómo puedo aprender sobre la creación / comprensión de algoritmos de negociación de acciones?
- ¿Cómo mejoro mis habilidades informáticas? ¿Alguien puede recomendarme formas de acortar la curva de aprendizaje?
- ¿Cuáles son algunos algoritmos de gráficos más utilizados en aplicaciones del mundo real?
Puede encontrar más detalles de la solución aquí. 🙂