0

这是问题：

a 二维数组relation[n][2]表示节点之间的关系，例如relation[0]等于{2,4}，所以节点2和节点4之间存在邻接关系，不包含循环关系.

我想将树结构保存在哈希图中，所以我尝试编写如下代码：

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);
        }
    }

似乎它不起作用，但我不知道如何解决它，有人可以帮助我吗？谢谢！

4

2 回答 2

1

代码代码有效（我测试过），除了有一个小的打字错误。

Map<Integer, LinkedList<Integer>>

按原样声明，地图中的值应该是 some LinkedList。

但是在这里，你放了一些List：

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

所以要么像这样创建一些 LinkedList ：

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

或声明您Map将 somesList作为值：

Map<Integer, List<Integer>>

注意：从 Java 8 开始，您可以Map.computeIfAbsent这样使用：

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);
}
于 2017-04-11T12:54:46.873 回答
0

试试这个方法。甚至可以处理数组确实多次定义边的情况（这是可能的）：

//          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);
}

输出

{1=[2, 3, 4], 2=[1, 5], 3=[1, 6, 7], 4=[1, 8], 5=[2], 6=[3], 7=[3], 8=[4]}
于 2017-04-11T13:08:57.883 回答