java - 将 map 用于图形

Question

您好，我打算为一门类(class)实现图形数据结构(图形不是要求的一部分，我选择使用它来解决问题)，我的第一个想法是使用邻接表，因为它需要更少的内存，而且我不希望我的图中有那么多边。

但后来我想到了。我可以使用 Map(具体来说是 HashMap)实现邻接表 Graph 数据结构。我没有顶点列表，而是有一个顶点映射，然后它包含一个简短的顶点边列表。

这似乎是适合我的方式。但我想知道是否有人能看到像我这样的学生在为此使用 HashMap 时可能错过的任何缺点？ (不幸的是，我记得我们在检查 HashMap 时非常疲倦......所以我对它们的了解少于我所知道的所有其他数据结构。)所以我想确定。

顺便说一句，我正在使用 Java。

Answer 1

表示图的两种主要方式是:

• 使用邻接表(如您所述)
• 与邻接矩阵

因为你不会有太多边(即代表你的图的邻接矩阵将稀疏)，我认为你决定使用列表而不是矩阵是一个很好的决定，因为你说过，它确实会占用更少的空间，因为没有空间被浪费来表示不存在的边缘。此外，Map 方法似乎是合乎逻辑的，因为您可以将图形的每个 Node 映射到它所在的 Node 列表连接的。另一种选择是让每个 Node 对象都包含它所连接的节点列表作为数据字段。我认为这两种方法中的任何一种都可以很好地工作。我总结如下。

第一种方法(维护 map ):

Map<Node, Node[]> graph = new HashMap<Node, Node[]>();

第二种方法(数据内置到Node类中):

public class Node {
    private Node[] adjacentNodes;
    public Node(Node[] nodes) { adjacentNodes = nodes; }
    public Node[] adjacentNodes() { return adjacentNodes; }
}