Comparar dos estructuras arbóreas

13

Me resulta difícil tratar de describir esto en términos correctos, así que daré tantos detalles como sea posible y espero que alguien sepa lo que estoy tratando de hacer = -)

Estoy tratando de comparar dos árboles de nodos para determinar qué tan similares / diferentes son en cuanto a estructura. En mis diagramas a continuación, ambos ejemplos tienen el mismo número de hijos, nietos, etc. En el ejemplo 1, Root tiene un hijo con dos hijos, pero en el ejemplo dos, la raíz no.

Probablemente podría descubrir cómo recorrer recursivamente y contar cuántos de cada nivel hay y comparar eso, dándome una idea de cuán similares son los árboles, pero solo haciéndolo de esa manera, parecerá que son idénticos, pero de hecho no lo son.

¿Alguien sabe sobre esto? ¿O incluso cuál es el término técnico para lo que es esto?

Editar: Además, esto está en C # y estoy usando Listas para almacenar estos objetos y sus hijos.

Ejemplo 1

ingrese la descripción de la imagen aquí

Ejemplo 2

ingrese la descripción de la imagen aquí

algorithm data-structure Mungoid
fuente
1
¿Qué estás tratando de lograr realmente? Esto suena un poco como un problema XY .
msell
La mejor manera de describirlo es comparar las estructuras 'moleculares' que el usuario crea una molécula a la vez. El ejemplo 1 sería una estructura creada por un usuario y el ejemplo 2 podría ser parte de una lista de estructuras predefinidas para ayudar a determinar si el usuario creó la estructura correcta. El isomorfismo del árbol raíz es aparentemente lo que estaba buscando = -)
Mungoid

Respuestas:

11

Lo que está buscando es el isomorfismo de árbol enraizado, que es una versión especializada del isomorfismo de gráficos , a excepción de los árboles y el nodo raíz es fijo.

La explicación dada en esta asignación usa dos propiedades:

  • Tener el mismo número de niveles (distancia entre los nodos raíz y hoja)
  • Cada nivel tiene el mismo número de nodos

Usando estas dos propiedades, avance desde las hojas hasta la raíz, etiquetando cada nodo con el número de hijos, en orden lexicográfico. Por ejemplo, su raíz en el ejemplo 1 estará etiquetada (0, 0, (0, 1)): tiene tres hijos, el primero / segundo tiene 0 hijos y el tercero tiene 2 hijos que tienen 0 y 1 hijos respectivamente. Finalmente, solo compara las etiquetas de la raíz para ver si los árboles son iguales.

No he hecho este tipo de tema y solo leí este artículo hace unos minutos, así que no puedo garantizar su corrección; Espero que ayude de todos modos.

congusbongus
fuente
¡Impresionante, eso es exactamente lo que estoy buscando! Tendré que intentarlo. ¡Gracias!
Mungoid
Creo que esto solo funciona si tienes un nodo raíz, pero en este caso ese podría ser el caso: D +1
Roy T.
Si no se proporciona el nodo raíz, aún puede utilizar esta técnica, pero pruebe con cada raíz. Al comparar dos árboles, esto significa repetir hasta n veces.
congusbongus
Sí, funcionó como un encanto. Tomó un poco de tiempo entenderlo, pero funciona perfecto = -)
Mungoid
Gracias por esto, parece algo que también podría usar, me encanta el algoritmo para encontrar el Centro de un árbol. Muy inteligente.
oodavid
4

El problema para ver si dos gráficos son lógicamente iguales se llama Graph Isomorphishm, por lo que es posible que desee comenzar desde allí.

Tenga en cuenta que el problema general del isomorfismo gráfico está en NP, sin embargo, para este caso especial puede haber un atajo, no estoy seguro, ya que parece lógico que para conocer las diferencias hay que verificar si son iguales.

Roy T.
fuente
Sí, eso es lo que necesito. Nunca habría descubierto cómo se llamaba eso. Gracias = -)
Mungoid