代码之家 › 专栏 › 技术社区 › NoProg

用邻接柱状图实现图

prims-algorithm hashtable graph data-structures algorithm

NoProg · 技术社区 · 7 年前

我想用Java实现一个Graph类 AdjacencyLists ,我将使用最小生成树上的这个类 Prim's 算法。

我读到有很多方法可以做到这一点,但我不能使用基于更简单的原始数据类型的数据结构( LinkedList ,堆栈等)所以我想也许一个好的解决方案是使用 HashTable 并将它们与 ArrayList 而不是 链表 .

我读到合并的目标 链表 具有 散列表 正在融合 链表 (顶点邻接列表的最佳枚举)和 散列表 (快速搜索和添加边)。

我想知道两件事:

我会使用ArrayList而不是LinkedList来保持这些礼节吗?
使用链接到另一个哈希表的哈希表会更好吗?

还有其他建议吗?如果我使用 散列表 ,解决碰撞的最佳方法是什么?我在考虑分开锁链。

1 回复 | 直到 7 年前

LyteFM 7 年前

我假设你想要的图形结构是 HashTable<Vertex,ArrayList<Pair<Vertex,Float>>> 使用边权重将每个顶点映射到其相邻顶点。

可以使用ArrayList,因为不需要从邻接列表中删除处理过的边。

一般来说,由于内存的使用,我不建议将哈希表链接到第二个哈希表,因为该算法处理顶点的所有相邻边。仅当要删除已处理的边时,它才有助于删除另一个方向的边。

请注意,虽然HashMap+ArrayList方法节省空间,并且对于该算法来说已经足够了 to run in O(V^2) ,当需要许多边查找时,不建议将其用于密集图。检查从A到B的边是否存在与A或B的相邻顶点数成线性关系。如果要在O(1)中检索它们,则需要第二个哈希表来存储边。文中给出了一个例子 JGraphT Library .

还要注意的是,这通常是推荐的 to use HashMap over HashTable

推荐文章

Rosie Lomas · 在ggplot中设置数字刻度

2 年前

Mahin Rahman · 我的培训和测试图表保持不变,有人能帮我解释一下,或者解释一下我哪里出错了?

3 年前

nedlaback · 在O(V+E)图中寻找瓶颈边

7 年前

Skampak · R visNetwork:创建新类型的边

7 年前

Habil Ganbarli · 在完整图上进行MST聚类(用于余弦相似性)

7 年前

Vaibhav · 在r Shinny中的Visnetwork中撤消单击事件

7 年前

Anuja · 长度l在R中的最短路径

7 年前

Cbhihe · 优化Neo4j查询,有条件地创建新关系

7 年前

fghjk · 绘制轨迹(python)

7 年前

LBerger · 计算图形图像中的名称使用(TensorBoard)

7 年前