我正在尝试创建一个由 Hashtable
支持的简单有向图数据结构,如下所示:
private Hashtable<V, List<Edge<V, K>>> adjacencyTable;
其中 V
是顶点类型,K
是边中存储的数据。 Edge
类简单地存储对它之间的两个顶点的引用以及一些 K
类型的对象。所以……
1 | (1, 2, data_1), (1, 3, data_2)
2 | (2, 3, data_3)
3 | (3, 1, data_4)
所以为了做一些像 removeVertex(3)
这样简单的事情,我必须遍历每个顶点的所有边,检查它们的 to
属性是否等于我要删除的顶点,然后删除它们。有没有更好的方法来实现这样的事情?
最佳答案
是的,你是对的,这是一个尴尬的选择。考虑改用
Map<V, Map<V, K>> adjacencies = new Hashmap<>();
与p
相邻的节点是adjacencies.get(p).keyset()
,边的数据是p->q
是 adjacencies.get(p).get(q)
。
删除顶点 r
必然是一个棘手的操作,因为您需要删除 r
的入边和出边。但是,您可以通过维护一个并行的“反向邻接”列表来加快速度。
Map<V, Set<V>> reverseAdjacencies = new Hashmap<>();
每次添加邻接 p->q
时,如下所示:
Map<V, K> edgesFromP = adjacencies.get();
if (edgesFromP == null) {
edgesFromP = new HashMap<>();
adjacencies.put(p, edgesFromP);
}
edgesFromP.put(q, nodeData);
反向 map 也需要更新,类似
Set<V> edgesToQ = reverseAdjacencies.get(q);
if (edgesToQ == null) {
edgesToQ = new HashSet<>();
reverseAdjacencies.put(q, edgesToQ);
}
edgesToQ.add(p);
现在删除节点r
,
// Remove the in-edges to r.
for (V p : reverseAdjacencies.remove(r)) {
adjacencies.get(p).remove(r);
}
// Remove r and all its out-edges
adjacencies.remove(r);
我省略了空检查等细节。
关于java - 在邻接表中存储边缘数据?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43729181/