Discussion :

[ptit_fumiste]

Bonjour à tous!
Voilà, j'ai une petite question à propos de la génération aléatoire d'arêtes formant un graphe.
L'objet Arete a les attributs suivants :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
private int sommet1;
private int sommet2;
private int poids;

Je génère une liste d'arêtes avec l'objet Random qu'on utilise pour chaque attribut d'une arête (en fonction du nombre connu de sommets du graphe bien sur).
Le problème est que je me retrouve avec des doublons (du genre {1, 2, 99}, {1, 2, 20}) : deux arêtes correspondants à deux sommets identiques avec un poids différent.
Ma question est : doit-on parcourir la liste à chaque génération d'arête pour vérifier qu'elle n'existe pas déjà, et si oui quelle est la structure de donnée la plus performante pour un gros volume (du genre 1500 arêtes)? J'aimerai éviter les tableaux de type Vector, pas performant dans le temps quand il y a beaucoup de données.
Si non, y a-t-il un autre méthode?
Merci d'avance

[Deaf]

Bonjour,

tu peux utiliser simplement une matrice d'int:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

int[][] poids;

Ainsi, le poids entre le sommet x et le sommet y sera:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

poids[x][y]

Cette structure te permet de travailler avec un graphe orienté et avoir:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

poids[x][y] != poids[y][x]

Le seul "inconvénient" de cette structure, c'est que tu as 'n' valeurs inutiles (ou 'n' est le nombre de sommets) : la diagonale.
Cela me semble quand même négligeable à côté de la taille de la matrice.

[ptit_fumiste]

Merci beaucoup, effectivement, il n'y a pas plus rapide que les tableaux. Et ça m'évite les doublons dans les arêtes!
Problème résolu

[benratti]

Une autre possibilité est de passer par une implémentation d'ensemble basé sur le hashCode (HashSet ou HashMap par exemple).

Il te faut alors redéfinir la méthode hashcode en fonction de tes sommets et ne pas tenir compte du poid de l'arrête.

L'implémentation avec un tableau n'est pas forcement la meilleur car l'initialisation du tableau (1500 * 1500) n'est pas anodine, et surtout cela est inutile si ton graphe n'est pas dense.

[ptit_fumiste]

Dommage, je viens de voir ta réponse :S
Je ne connaissais pas l'usage du hashcode, mais j'avoue que ca change ma vision des choses.
Je garde sous le coude pour la prochaine fois