liste de contiguïté d'un graphe pondéré dirigé

Question

J'utilise des listes de contiguïté pour représenter un graphe pondéré dirigé et en fonction du code exemple fourni par this SO question, je l'ai créé les éléments suivants:

import java.util.HashMap; 
import java.util.LinkedHashSet; 
import java.util.LinkedList; 
import java.util.Map; 
import java.util.Set; 

public class _Graph { 
    private Map<String, LinkedHashSet<HashMap<String, Integer>>> map = new HashMap<String, LinkedHashSet<HashMap<String, Integer>>>(); 

    public void addEdge(String node1, String node2, int dist) { 
     LinkedHashSet<HashMap<String, Integer>> adjacent = map.get(node1); 
     HashMap<String, Integer> innerMap = new HashMap<String, Integer>(); 
     if(adjacent==null) { 
      adjacent = new LinkedHashSet<HashMap<String, Integer>>();      
      map.put(node1, adjacent); 
     } 
     innerMap.put(node2, dist); 
     adjacent.add(innerMap); 
    } 

    public boolean isConnected(String node1, String node2) { 
     Set<HashMap<String, Integer>> adjacent = map.get(node1); 
     if(adjacent==null) { 
      return false; 
     } 
     return adjacent.contains(node2); 
    } 

    public LinkedList<HashMap<String, Integer>> adjacentNodes(String node) { 
     LinkedHashSet<HashMap<String, Integer>> adjacent = map.get(node); 
     if(adjacent==null) { 
      return new LinkedList<HashMap<String, Integer>>(); 
     } 
     return new LinkedList<HashMap<String, Integer>>(adjacent); 
    } 

} 

Je ne parviens pas à rendant la méthode isConnected pour fonctionner correctement. Est-ce que j'utilise une mauvaise structure de données pour représenter le graphique ici (Map<String, LinkedHashSet<HashMap<String, Integer>>>)? Le hashmap tiendra le nom du noeud connecté et la distance à elle:

Map<startNode, LinkedHashSet<HashMap<endNode, distanceToEndNode>>> 

1. Fondamentalement, comment puis-je vérifier si un nœud appartient à la liste de contiguïté d'un noeud de base donnée ? Je pense que le problème est réduit à itérativement correctement au cours de la structure Set<HashMap<String, Integer>> , ou est-ce que mon raisonnement est faux?
2. Dans ma deuxième méthode adjacentNodes(String node) Je suis retour une liste chaînée contenant les cartes (dans une structure de jeu) des noeuds connectés et leurs distances. Comment pourrais-je efficacement parcourir pour voir toutes les connexions d'un nœud donné?

Answer 1

Je pense que LinkedHashSet n'est pas nécessaire ici, vous pouvez représenter le graphique avec juste Map<String, Map<String, Integer>>.

isConnected est essentiellement ce que vous avez déjà:

public boolean isConnected(String node1, String node2) { 
    Map<String, Integer> adjacent = map.get(node1); 
    if(adjacent==null) { 
     return false; 
    } 
    return adjacent.containsKey(node2); 
} 

adjacentNodes a juste besoin de tirer les entrées dans le jeu de hachage pour le noeud source

public Collection<Map.Entry<String, Integer>> adjacentNodes(String node) { 
    Map<String, Integer> adjacent = map.get(node); 
    if(adjacent==null) { 
     return new ArrayList<Map.Entry<String, Integer>>(); 
    } 
    return adjacent.entrySet(); 
}