Java PriorityQueue semble être dans le mauvais ordre

Question

J'essaie de faire un programme qui résout le problème de Spanning Tree minimum. Pour ce faire, j'ai une file d'attente prioritaire d'objets Edge qui devraient être triés en fonction de leur poids correspondant (après cela, cela n'a pas vraiment d'importance, mais je suis passé par des noms de nœuds). J'utilise java.util.PriorityQueue. J'ai essayé à peu près tout mais je ne peux pas penser à mettre en œuvre la fonction compareTo() fonctionne. Il trie la plupart des bords correctement, mais pas tous. Voici le code de la fonction compareTo() les plus élémentaires que je pouvais penser:

@Override 
public int compareTo(Object other) { 
    return toString().compareTo(((Edge) other).toString()); 
} 

Les sorties de fonction toString() d'abord le poids, puis les deux noeuds, donc si deux noeuds A et B ont été connectés avec le poids 4, il génèrerait

4AB 

Après avoir mis dans un graphique échantillon je finis avec la file d'attente de priorité suivant:

[1AB, 1BA, 1FH, 2CB, 1CG, 1GC, 1HF, 2EB, 2CD, 3EG, 2BC, 2BE, 3AC, 2GH, 2HG, 5AD, 5EC, 3ED, 2EF, 5CE, 4FD, 2FE, 4FG, 5DA, 2DC, 3GE, 4GF, 3DE, 3CA, 4DF] 

Il est clair que ce n'est pas en orde mais, fondamentalement, toute méthode de comparaison à laquelle je peux penser aboutit à ce résultat.

Answer 1

Il n'y a rien de mal ici. Ce que vous imprimez semble être le résultat de toString(), qui n'est pas garanti d'être dans un ordre particulier. Lorsque vous consommez la file d'attente en supprimant ou jetant un coup d'œil en tête, un élément minimal — tel que défini par votre comparateur — résultera. La file d'attente dans son ensemble n'est pas ordonnée; l'ordre détermine uniquement la tête de la file d'attente, et seules certaines opérations spécifiées pour fonctionner sur la tête sont affectées par la commande. Les méthodes toString() et iterator() ne font pas partie de ces opérations. Votre comparateur doit comparer les poids numériquement, plutôt que sous forme de chaînes. Utiliser la comparaison de cordes pour le bord comme un tie-breaker pour les bords de poids égal est correct, mais considérez si vous aurez deux bords avec des directions opposées, et s'ils ont besoin d'un soin particulier.