J'ai une structure de type forte> cyclique forte> représentée par des objets noeud em>.
Un nœud em> est une valeur scalaire (feuille) ou une liste de n> = 1 nœudes em> (nœud interne). en raison des références circulaires possibles, je ne peux pas Utilisez simplement une fonction de hashcode récursif (), qui combine le hashcode () de tous les nœuds d'enfants: cela se retrouverait dans une récursion infinie. P> tandis que la partie Hashcode () semble au moins être faisable en signalant le signal et ignorer les nœuds déjà visités, j'ai des problèmes de penser à un algorithme fonctionnant et efficace pour des égaux (). P> à ma surprise, je n'ai trouvé aucune information utile à ce sujet, mais je suis sûr que je suis sûr Beaucoup de gens intelligents ont pensé à de bonnes façons de résoudre ces problèmes ... Droite? P> Exemple (Python): P> A = [ 1, 2, None ]; A[2] = A
B = [ 1, 2, None ]; B[2] = B
3 Réponses :
Si vous pensez à ce sujet sous forme de graphique, un nœud de feuille est un nœud qui n'a qu'une seule connexion et un nœud complexe en est un avec au moins 2. Donc, vous l'avez eu de cette façon, mettez-en une simple sorcière d'algorithme BFS applique le hachage fonction à chaque nœud qu'il passe puis dépose le résultat. De cette façon, vous vous assurez que vous ne tomberez pas dans des cicles ou de passer à travers n'importe quel noeud d'une fois.
La mise en œuvre pourrait être très straihgtforward. Lisez-y ici .
Merci pour votre réponse, mais cela ne m'aidait pas vraiment:
Je ne peux pas calculer le hachage d'un nœud avant que je connaisse le hachage de tous ses enfants. Avec un BFS ou des DFS, je peux éviter la récursion infinie, mais le hachage que je reçois peut ne pas être bon si il y a des cycles: par exemple, lorsque j'ignore les nœuds que je vois une seconde fois, le hachage d'un nœud serait le même comme d'un nœud sans le cycle. Je cherchais un algorithme de hachage qui a du sens et n'introduit pas de collisions inutiles (si cela existe pour cette affaire).
Vous devez marcher sur les graphiques.
Voici une question: ces graphiques sont-ils égaux? Si tel est le cas, vous avez besoin d'un ensemble de tuples (nœud, nœuds). Utilisez cet ensemble pour attraper des boucles et renvoyez «vrai» lorsque vous attrapez une boucle. Sinon, vous pouvez être un peu plus efficace et utiliser une carte du nœud au nœud. Ensuite, lors de la marche des graphiques, accumulez un ensemble de correspondances. (Dans le cas ci-dessus, A correspondent à B, A [2] correspondrait à B [2], & c.) Ensuite, lorsque vous visitez une paire de nœuds, vous assurez que la paire exacte est sur la carte; Si ce n'est pas le graphique ne correspond pas.
J'aimerais connaître une bonne réponse aussi. Jusqu'à présent, j'utilise une solution basée sur l'ensemble visité.
Lorsque vous calculez Hash, je traverse la structure graphique et je garde un ensemble de nœuds visités. Je n'entre pas deux fois le même noeud. Lorsque je frappe un nœud déjà visité, le hachage retourne un numéro sans récursion.
Ce travail, même pour la comparaison sur l'égalité. Je comparais les données de nœud et invoquer récursivement sur les enfants. Lorsque je frappe un nœud déjà visité, la comparaison renvoie True sans récursion.