java - 在邻接表中存储边缘数据？

Question

我正在尝试创建一个由 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 属性是否等于我要删除的顶点，然后删除它们。有没有更好的方法来实现这样的事情？

Answer 1

是的，你是对的，这是一个尴尬的选择。考虑改用

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);

我省略了空检查等细节。