Comparando duas estruturas em árvore

13

Estou tendo dificuldades para descrever isso em termos corretos, por isso darei o máximo de detalhes possível e espero que alguém saiba o que estou tentando fazer = -)

Estou tentando comparar duas árvores de nós para determinar quão semelhantes / diferentes elas são em termos de estrutura. Nos meus diagramas abaixo, os dois exemplos têm o mesmo número de filhos, netos etc. No exemplo 1, o Root tem um filho com dois filhos, mas no exemplo dois, o Root não.

Provavelmente, eu poderia descobrir como fazer um loop recursivo e contar quantos de cada nível existem e compará-los, dando-me uma idéia de como as árvores são semelhantes, mas apenas fazendo dessa maneira, parecerá que são idênticas, mas na verdade eles não são.

Alguém sabe disso? Ou mesmo qual é o termo técnico para o que é isso?

Edit: Além disso, isso está em c # e eu estou usando listas para armazenar esses objetos e seus filhos.

Exemplo 1

insira a descrição da imagem aqui

Exemplo 2

insira a descrição da imagem aqui

algorithm data-structure Mungoid
fonte
1
O que você está realmente tentando alcançar? Isso parece um pouco com o problema XY .
msell
A melhor maneira de descrever é comparando estruturas 'moleculares' que o usuário cria uma molécula de cada vez. O exemplo 1 seria uma estrutura criada por um usuário e o exemplo 2 poderia fazer parte de uma lista de estruturas predefinidas para ajudar a determinar se o usuário criou a estrutura correta. Isomorfismo árvore de raiz é aparentemente o que eu estava procurando = -)
Mungoid

Respostas:

11

O que você está procurando é isomorfismo de árvore enraizada, que é uma versão especializada do isomorfismo de gráfico , exceto para árvores e o nó raiz é fixo.

A explicação dada nesta tarefa usa duas propriedades:

  • Possuem o mesmo número de níveis (distância entre os nós da raiz e da folha)
  • Cada nível tem o mesmo número de nós

Usando essas duas propriedades, suba das folhas até a raiz, rotulando cada nó com o número de filhos, em ordem lexicográfica. Por exemplo, sua Raiz no Exemplo 1 será rotulada (0, 0, (0, 1)) - ela possui três filhos, o primeiro / segundo possui 0 filhos e o terceiro possui 2 filhos com 0 e 1 filhos, respectivamente. Finalmente, basta comparar os rótulos das raízes para ver se as árvores são iguais.

Não fiz esse tipo de assunto e só li este artigo alguns minutos atrás, por isso não posso garantir sua correção; espero que ajude de qualquer maneira.

congusbongus
fonte
Impressionante, isso é exatamente o que estou procurando! Vou ter que tentar. Obrigado!
Mungoid
Eu acho que isso só funciona se você tem um nó raiz, mas, neste caso, que pode ser o caso: D 1
Roy T.
Se o nó raiz não for fornecido, você ainda poderá usar esta técnica, mas tente todas as raízes. Ao comparar duas árvores, isso significa repetir até n vezes.
precisa saber é o seguinte
Sim, funcionou como um encanto. Tomou um pouco de tempo para entender isso, mas funciona = perfeitos -)
Mungoid
Obrigado por isso, parece algo que eu também poderia usar, estou adorando o algoritmo para encontrar o Center of a Tree. Muito esperto.
Oodavid
4

O problema para ver se dois gráficos são logicamente iguais é chamado Isomorfismo de Gráfico; portanto, você pode querer começar a partir daí.

Observe que o problema geral de isomorfismo de gráfico está em NP; no entanto, para este caso especial, pode haver um atalho, não tenho certeza, pois parece lógico que para conhecer as diferenças que você precisa verificar se são iguais.

Roy T.
fonte
Sim, é disso que eu preciso. Nunca teria descoberto como aquilo era chamado. Obrigado = -)
Mungoid