1

我最近开始编写一个用于建模图的工具（节点和边，都由对象表示，而不是邻接矩阵或简单的数字），以便在研究生院旁边的软件开发中获得一些实践。我希望一个节点知道它的邻居和它所发生的边缘。一个明显的方法是使用 HashSet 和 HashSet。然而，我想做的是有一个方法

Node_A.getEdge(Node B)

在 O(1) 中返回节点 A 和 B 之间的边。我正在考虑通过使用一个 HashMap 替换上面提到的两个 HashSet 来做到这一点，该 HashMap 将邻居映射到连接节点与其邻居的边。例如，调用

Node_A.hashmap.get(B)

应该返回连接 A 和 B 的边缘。我的问题是是否有办法

HashMap.keySet().contains(Node A);
HashMap.values().contains(Edge e);

两者都在 O(1) 中工作？如果标准库不是这种情况，是否有实现会给我恒定的时间来添加、删除、包含、keySet() 和 values() 的大小？

4

2 回答 2

1

尽量不要过度思考这一点。例如，您说您在 A 和 B 之间获得优势Node_A.getEdge(Node B)。但通常它是A->B信息被认为是边缘。（所以你需要你应该检索的信息。）

你说你想要 O(1)，可以理解，显然存储邻接矩阵只会给你 O(n)，所以你不能使用它；但是，在每个节点对象中存储相邻节点列表的第二个最明显的选择已经为您提供了您想要的。（注意：这与拥有一个会给你 O(n) 的全局邻接列表不同）。

于 2012-10-20T18:59:20.073 回答
1

正如 AmitD 所说，HashSet 和 HashMap 对于 contains、get 和 put 已经有了固定的时间。如果您HashMap.valueSet().contains(Edge e)可以尝试查看 Google Guava 库中的HashBiMap。

于 2012-10-20T19:00:02.370 回答