Algorithme pour la structure de graphe/de données sur Java

Question

J'ai travaillé sur le problème suivant où, j'ai un fichier CSV avec deux colonnes, nous pouvons dire que les noms classés sont "amis". Les deux colonnes contiennent des lettres de A à Z. par ex.

A B 
B C 
A E 
D F 
E F 

Chaque ligne a deux lettres différentes (pas de duplication dans la rangée). A est un ami de B, C est un ami de D etc ... Si la personne A parle à la personne B et la personne B parle à la personne C, alors B et C deviendront des aquitances. Aquintaces sont qui partagent un ami commun. J'ai besoin d'aileron qui a plus d'aquintances?

J'ai essayé avec deux méthodes différentes en utilisant des structures de données différentes comme hashmap, arraylist, stack etc, et une autre utilisant la théorie des graphes (bibliothèque JGraphT). Mais, je suis bloqué avec la logique si j'utilise des strcutres de données et je suis coincé avec traversal dans le graphique si j'utilise la théorie des graphes.

J'ai des questions suivantes: -

1. Quelle est la meilleure approche pour aller avec des structures de données ou graphique? Ou une autre meilleure approche/logique/algorithme que cela?
2. Est-ce que quelqu'un sait comment parcourir un graphe dans la bibliothèque JgraphT? Je suis pas en mesure de le faire, ils ont une documentation très limitée sur la bibliothèque.

S'il vous plaît, toute aide serait vraiment appréciée.

Answer 1

Vous pouvez d'abord avoir une table de hachage qui mappe chaque lettre à l'ensemble de ses amis, par ex. A correspond à {B}, B correspond à {C}, et si Z a deux amis Y et W alors Z correspond à {Y, W}. Ceci est une carte de hachage de lettres à des ensembles de lettres.

Pour calculer les connaissances, parcourir la carte de hachage. Quand vous êtes à l'entrée A -> {B, C, F} alors itérer dans une boucle interne à travers l'ensemble B, C, F. Recueillir leurs amis (trois ensembles) dans un seul ensemble (il suffit d'insérer les éléments dans un ensemble de temp) et retirez A de cet ensemble si A a été trouvé. La taille de cet ensemble est alors le nombre de connaissances pour A. Rincez et répétez.

Answer 2

Généralement, les HashMaps sont parmi les plus rapides et les plus faciles à utiliser. Je vous recommande de les utiliser plutôt que des bibliothèques personnalisées, sauf si vous êtes sûr que certaines bibliothèques feront facilement quelque chose dont vous avez besoin et quelque chose qui prendra du temps à coder.

Dans votre cas, vous pouvez simplement utiliser chaque personne comme une clé et la liste de ses amis comme l'objet pointé par. L'analyse de votre fichier .csv et le remplissage de la HashMap en conséquence résoudra votre problème, comme indiqué précédemment.