3

嗨，我打算为一门课程实现一个 Graph 数据结构（该图不是要求的一部分，我选择使用它来解决问题），我的第一个想法是使用邻接列表来实现它，因为这需要更少的内存，而且我不希望在我的图中有那么多边。

但后来我想到了。我可以使用 Map（HashMap具体来说）实现邻接列表 Graph 数据结构。而不是顶点列表，我将有一个顶点映射，然后保存一个短边列表到顶点。

这似乎是我要走的路。但我想知道是否有人能看到像我这样的学生在使用 a 时可能错过的任何缺点HashMap？（不幸的是，我记得在我们复习的时候很累HashMap……所以我对它们的了解少于我所知道的所有其他数据结构。）所以我想确定一下。

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

4

2 回答 2

9

表示图形的两种主要方式是：

  • 与邻接列表（如您所述）
  • 与邻接矩阵

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

第一种方法（维护地图）：

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; }
}
于 2012-08-30T02:16:27.697 回答
7

图传统上通过邻接列表或邻接矩阵表示（还有其他针对某些图形格式进行优化的方法，例如，如果节点 ID 是按顺序标记的和/或您提前知道节点/边的数量，但我不会进入那个）。

在邻接列表和邻接矩阵之间进行选择取决于您的需要。显然，邻接矩阵将比邻接列表占用更多空间（矩阵将始终占用（节点数）^ 2，而列表将占用（节点数 + 边数），但如果您的图形“小”，那么这并没有什么不同。

另一个问题是你有多少边（你的图是稀疏的还是密集的）？您可以通过获取您拥有的边数并将其除以：

n(n-1) / 2

其中“n”是图的节点数。上面的等式在“n”节点 UNDIRECTED 图中找到总的可能边数。如果图形是有向的，去掉“/2”。

要考虑的其他事情是有效的边缘成员资格是否重要。邻接列表可以轻松检测边缘成员资格（O（1）），因为它只是一个数组查找 - 对于邻接列表，如果“列表”存储为除 a 以外的其他内容，HashSet它会慢得多，因为您必须查看整个边缘列表。或者也许你保持边缘列表的排序，你可以做一个二进制搜索，但是边缘插入需要更长的时间。也许您的图非常稀疏，并且邻接矩阵使用了太多内存，因此您必须使用邻接列表。很多事情要考虑。

还有很多可能与您的项目有关的问题，我只列出一些。

通常，假设您的图不是很复杂或“大”（在数百万个节点的意义上），HashMap其中键是节点 ID，值是节点 ID 的一个Set或其他一些集合，指示键的邻居节点很好，我已经在 8gb 机器上为 400,000 多个节点图完成了此操作。基于的HashMap实现可能是最容易实现的。

于 2012-08-30T03:14:04.837 回答