我正在考虑在内存中表示图形的方法吗?
我曾考虑使用哈希图的哈希图,以便其行为类似于到邻接矩阵,但是我们可以使用可比较边缘标签,而不仅仅是整数。
在广度优先搜索和Dijkstra的算法中,我们必须遍历邻接表并将节点添加到队列中。这导致了我的问题:
与Java中的常规HashSet相比,通过链接的哈希集进行迭代的效率要高吗?
似乎是因为每个节点之间的链接都按它们添加的顺序排列,所以如果它们存在,我们就不必遍历空容器(取决于HashMap的重新哈希比,这可能是或多或少)。这将使我们能够将邻接矩阵的随机访问行为与邻接列表的搜索算法效率相结合。
是,您是对的。
Java HashMap / Set在稀疏图中的性能较差,因为它必须从空容器中进行迭代。当大多数节点仅连接另一个节点时。 HashMap / Set可能需要8次迭代才能获得准确的结果。相关分析可以在Codeforces: Performance of hash set iterators in different programming languages。
为了表示图,Java通用机制可以让您为原始类型创建对象类型,例如Integer。当转换为基本类型并构建图形时,它们将降低性能。在最佳实践中,您需要使用Trove或其他库。也许,请自己实施。