图的Hashmap表示

Question

例如,我有一个带图形边的文本文件

1 2

1 3

2 5

等,并希望以某种方式表示我的图表.我试图使用hashmap,它是表示边缘的最佳方式吗？第二个问题,我如何访问我的hashmap中的第一个和第二个条目？我的代码在这里

    DataInputStream dStream = new DataInputStream(new FileInputStream("C:/Programming/Java/test.txt"));
    BufferedReader bReader = new BufferedReader(new InputStreamReader(dStream));

    HashMap<Integer, Integer> graphEdges = new HashMap<Integer, Integer>();
    String line;
    while( (line = bReader.readLine()) != null) {
        String[] firstSecond = line.split(" ");
        int firstDigit = Integer.parseInt(firstSecond[0]);
        int secondDigit = Integer.parseInt(firstSecond[1]);

        graphEdges.put(firstDigit, secondDigit);
    }

    System.out.println(graphEdges);

    bReader.close();
}

Answer 1

在图的许多可能表示中,2基本如下:

• 邻接列表

在Java中:

Map<Integer, List<Integer>> graph = new HashMap<>();
...
while( (line = bReader.readLine()) != null) {
    String[] tokens = line.split(" ");
    int firstNode = Integer.parseInt(tokens[0]);
    int secondNode = Integer.parseInt(tokens[1]);

    if(!graph.containsKey(firstNode)) graph.put(firstNode, new LinkedList());
    graphEdges.get(firstNode).add(secondNode);
}

• 邻接矩阵

在Java中:

int[][] graph = new int[numberOfNodes][numberOfNodes];
while( (line = bReader.readLine()) != null) {
    String[] tokens = line.split(" ");
    int firstNode = Integer.parseInt(tokens[0]);
    int secondNode = Integer.parseInt(tokens[1]);

    graph[firstNode-1][secondNode-1] = 1;
    graph[secondNode-1][firstNode-1] = 1;
}

以下是这两种表示的操作和存储效率的比较:

                   |     Adjacency List    |   Adjacency Matrix   |
Storage            |      O(nodes+edges)   |     O(nodes^2)       |
Add node           |          O(1)         |     O(nodes^2)*      |
Add edge           |          O(1)         |        O(1)          |
Remove node        |        O(edges)       |     O(nodes^2)*      |
Remove edge        |        O(edges)       |        O(1)          |
isAdjacent(x1,x2)  |        O(nodes)       |        O(1)          |
*Requires copying of the whole array

您还可以在邻接列表中稍作修改,并使用HashSets而不是LinkedList来存储相邻节点.在这种情况下,除了isAdjacent(x1,x2)操作现在具有O(1)复杂度(摊销)之外,一切都是相同的.

Answer 2

AHashMap不适合这种情况，因为对于指定的键，您可以有一个值。您需要一个可以保存一个键的多个值的映射。Guava在Multimap中正是具有这个概念，并具有ArrayListMultimap之类的实现。