Comparaison de deux arborescences

13

J'ai du mal à décrire cela en termes corrects, je vais donc donner autant de détails que possible et j'espère que quelqu'un sait ce que j'essaie de faire = -)

J'essaie de comparer deux arbres de nœuds pour déterminer à quel point ils sont similaires / différents sur le plan de la structure. Dans mes diagrammes ci-dessous, les deux exemples ont le même nombre d'enfants, de petits-enfants, etc. Dans l'exemple 1, Root a un enfant avec deux enfants, mais dans l'exemple deux, root n'en a pas.

Je pourrais probablement comprendre comment parcourir de manière récursive et compter le nombre de chaque niveau et le comparer, en me donnant une idée de la similitude des arbres, mais en le faisant de cette façon, il semblera qu'ils sont identiques, mais en fait, ils ne le sont pas.

Quelqu'un sait-il cela? Ou même quel est le terme technique pour ce que c'est?

Edit: En outre, c'est en C # et j'utilise des listes pour stocker ces objets et leurs enfants.

Exemple 1

entrez la description de l'image ici

Exemple 2

entrez la description de l'image ici

algorithm data-structure Mungoid
la source
1
Qu'essayez-vous réellement de réaliser? Cela ressemble un peu au problème XY .
msell
La meilleure façon de le décrire est de comparer des structures «moléculaires», l'utilisateur crée une molécule à la fois. L'exemple 1 serait une structure créée par un utilisateur et l'exemple 2 pourrait faire partie d'une liste de structures prédéfinies pour aider à déterminer si l'utilisateur a créé la structure correcte. L'isomorphisme des racines est apparemment ce que je cherchais = -)
Mungoid

Réponses:

11

Vous recherchez un isomorphisme d'arbre enraciné, qui est une version spécialisée du isomorphisme graphique , à l'exception des arbres et le nœud racine est fixe.

L'explication donnée dans cette mission utilise deux propriétés:

  • Ont le même nombre de niveaux (distance entre les nœuds racine et feuille)
  • Chaque niveau a le même nombre de nœuds

En utilisant ces deux propriétés, montez des feuilles à la racine, en étiquetant chaque nœud avec le nombre d'enfants, dans l'ordre lexicographique. Par exemple, votre racine dans l'exemple 1 sera étiquetée (0, 0, (0, 1)) - elle a trois enfants, le premier / second a 0 enfant et le troisième a 2 enfants qui ont respectivement 0 et 1 enfant. Enfin, il vous suffit de comparer les étiquettes racine pour voir si les arbres sont les mêmes.

Je n'ai pas fait ce genre de sujet et je n'ai lu ce document qu'il y a quelques minutes donc je ne peux pas garantir son exactitude; j'espère que ça aide de toute façon.

congusbongus
la source
Génial, c'est à peu près exactement ce que je recherche! Je vais devoir essayer. Merci!
Mungoid
Je pense que cela ne fonctionne que si vous avez un nœud racine, mais dans ce cas, cela pourrait être le cas: D +1
Roy T.
Si le nœud racine n'est pas indiqué, vous pouvez toujours utiliser cette technique mais essayez chaque racine. Lorsque l'on compare deux arbres, cela signifie répéter jusqu'à n fois.
congusbongus
Oui, cela a fonctionné comme un charme. A pris un peu de temps pour le comprendre mais fonctionne parfaitement = -)
Mungoid
Merci pour cela, ça ressemble à quelque chose que je pourrais utiliser aussi, j'adore l'algorithme pour trouver le centre d'un arbre. Très intelligent.
oodavid
4

Le problème pour voir si deux graphiques sont logiquement identiques s'appelle Graph Isomorphishm , vous pouvez donc commencer par là.

Notez que le problème général d'isomorphisme graphique est dans NP mais pour ce cas spécial il peut y avoir un raccourci, je ne suis pas sûr car il semble logique que pour connaître les différences, vous devez vérifier si elles sont égales.

Roy T.
la source
Oui, c'est ce dont j'ai besoin. N'aurait jamais compris comment cela s'appelait. Merci = -)
Mungoid