Eth*_*han 3 java graph hashmap map data-structures
嗨,我正在为一门课程实现一个Graph数据结构(图表不是要求的一部分,我选择使用它来解决问题),我的第一个想法是使用邻接列表来实现它,因为这需要更少的内存,我不希望在我的图中有那么多的边.
但后来发生在我身上.我可以使用Map(HashMap具体)实现邻接列表Graph数据结构.而不是顶点列表,我将有一个顶点Map,然后将一个边的短边列表保存到顶点.
这似乎是我的方式.但是我想知道是否有人可以看到像我这样的学生在使用HashMap这个时可能错过的任何缺点？(不幸的是我记得在我们过去的时候非常疲惫HashMap...所以我对它们的了解比我所知道的所有其他数据结构要少.)所以我想确定.
顺便说一下,我正在使用Java.
表示图形的两种主要方式是:
由于你没有太多的边缘(即代表你的图形的邻接矩阵将是稀疏的),我认为你决定使用列表而不是矩阵是一个很好的,因为正如你所说,它确实会占用更少的空间因为没有空间浪费来代表缺席的边缘.此外,该Map方法似乎是合乎逻辑的,因为您可以将每个Node图形映射Node到它所连接的s 列表.另一种方法是让每个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; }
}
图传统上通过邻接列表或邻接矩阵表示（还有其他方法针对某些图格式进行了优化，例如如果节点 ID 是按顺序标记的和/或您提前知道节点/边的数量，但我不会涉及）。
在邻接列表和邻接矩阵之间进行选择取决于您的需要。显然，邻接矩阵将比邻接列表占用更多的空间（矩阵将始终采用（节点数）^ 2 而列表将采用（节点数 + 边数），但如果您的图是“小”那么这并没有什么区别。
另一个问题是你有多少条边（你的图是稀疏还是密集）？您可以通过获取您拥有的边数并将其除以来找到图形的密度：
n(n-1) / 2
其中“n”是图的节点数。上面的等式在“n”节点 UNDIRECTED 图中找到可能的边总数。如果图形是有向的，请删除“/2”。
还需要考虑的是，有效的边缘成员资格是否重要。邻接列表可以轻松检测边缘成员资格（O（1）），因为它只是一个数组查找 - 对于邻接列表，如果“列表”存储为除 a 以外的其他内容，HashSet它会慢得多，因为您必须查看整个边缘列表。或者也许您保持边缘列表的排序，您可以只进行二分搜索，但是边缘插入需要更长的时间。也许你的图很稀疏，邻接矩阵使用了太多内存，所以你必须使用邻接表。很多事情要考虑。
还有很多可能与您的项目有关的问题，我只列出了一些。
一般来说，假设您的图不是很复杂或“大”（在数百万个节点的意义上），HashMap其中键是节点 ID，值是一个Set或其他一些节点 ID 的集合，表示键的邻居节点很好，我已经在 8GB 机器上为 400,000 多个节点图做了这个。一个HashMap基于实现可能会是最容易实现的。