Comment puis-je sauvegarder une structure arborescente dans un hashmap?

Question

Voici la question:

une relation de tableau à deux dimensions [n] [2] représentent la relation entre les noeuds, par relation exemple [0] est égal à {2,4}, donc il y a une relation de adjancency entre le noeud 2 et le noeud 4 et ne contient pas de relation cyclique.

Je veux sauver la structure de l'arbre dans un hashmap, alors j'ai essayé d'écrire mon code comme ci-dessous:

Map<Integer, LinkedList<Integer>> graph = new HashMap<Integer, LinkedList<Integer>>(); 
    for (int i = 0; i < n; i++) { 
     int A = relation[i][0]; 
     int B = relation[i][1]; 
     if (graph.get(A) == null) { 
      List<Integer> tempList = new LinkedList(); 
      tempList.add(B); 
      graph.put(A, tempList); 
     } else { 
      graph.get(A).add(B); 
     } 
     if (graph.get(B) == null) { 
      List<Integer> tempList = new LinkedList(); 
      tempList.add(A); 
      graph.put(B, tempList); 
     } else { 
      graph.get(B).add(A); 
     } 
    } 

appearently cela ne fonctionne pas, mais je ne sais pas comment le résoudre, peut quelqu'un m'aider à pls? Merci!

Answer 1

Le code fonctionne (j'ai testé) sauf qu'il y a une petite erreur de frappe.

Map<Integer, LinkedList<Integer>> 

Déclaré en l'état, les valeurs de votre carte sont censés être un peu LinkedList.

Mais ici, vous mettre un peu List:

List<Integer> tempList = //[...]; 
[...] 
//Compiler will complain that tempList is a List but a LinkedList is expected. 
graph.put(A, tempList); 

donc créer soit une LinkedList comme ceci:

LinkedList<Integer> tempList = new LinkedList<>(); 

ou déclarer que votre Map prend Somes List comme valeurs:

Map<Integer, List<Integer>> 

Note: à partir de Java 8, vous pouvez utiliser Map.computeIfAbsent comme ceci:

Map<Integer, LinkedList<Integer>> graph = new HashMap<>(); 
for (int i = 0; i < n; i++) { 
    int A = relation[i][0]; 
    int B = relation[i][1]; 
    graph.computeIfAbsent(A, k-> new LinkedList<>()).add(B); 
    graph.computeIfAbsent(B, k-> new LinkedList<>()).add(A); 
} 

Answer 2

Essayez-le de cette façon. Poignées même cas lorsque le réseau ne définit les bords plusieurs fois (ce qui pourrait être possible):

//   1 
//  /| \ 
//  2 3 4 
// // \ \ 
//  5 6 7 8 
// 
public static void main(String[] args) { 
    int[][] tree = new int[][] { 
      {1, 2}, {1, 3}, {1, 4}, 
     {2, 5}, {3, 6}, {3, 7}, {4, 8} }; 

    Map<Integer, List<Integer>> map = new HashMap<>(); 
    for (int[] node : tree) { 
     addEdge(map, node[0], node[1]); 
     addEdge(map, node[1], node[0]); 
    } 

    System.out.println(map); 
} 

private static void addEdge(Map<Integer, List<Integer>> map, int key, int value) { 
    List<Integer> edges = map.computeIfAbsent(key, k -> new LinkedList<>()); 
    if (! edges.contains(value)) edges.add(value); 
} 

Sortie

{1=[2, 3, 4], 2=[1, 5], 3=[1, 6, 7], 4=[1, 8], 5=[2], 6=[3], 7=[3], 8=[4]}