PROSAGA码农传奇-边缘数据治理-将边缘数据存储在邻接列表中？

将边缘数据存储在邻接列表中？

作者: 757461156
发布时间: 2024-05-09 06:15:23 (2月前)
转自：

<div class =“post-text”itemprop =“text”>
  
    是的你是对的，这是一个尴尬的选择。考虑改为使用
  
   <pre>
 <code>
 Map<V, Map<V, K>> adjacencies = new Hashmap<>();

</code>
 </pre>
  
    邻近的节点
     <code>
 p
 </code>
     是
     <code>
 adjacencies.get(p).keyset()
 </code>
    和边缘的数据
     <code>
 p->q
 </code>
     是
     <code>
 adjacencies.get(p).get(q)
 </code>
    。
  
  
    删除顶点
     <code>
 r
 </code>
     一定是一个棘手的操作因为你需要删除它的内外边缘
     <code>
 r
 </code>
    。但是，您可以通过维护并行的“反向邻接”列表来快速完成。
  
   <pre>
 <code>
 Map<V, Set<V>> reverseAdjacencies = new Hashmap<>();

</code>
 </pre>
  
    每次添加邻接
     <code>
 p->q
 </code>
     有类似的东西：
  
   <pre>
 <code>
 Map<V, K> edgesFromP = adjacencies.get();
if (edgesFromP == null) {
 edgesFromP = new HashMap<>();
 adjacencies.put(p, edgesFromP);
}
edgesFromP.put(q, nodeData);

</code>
 </pre>
  
    反向地图也需要更新，例如
  
   <pre>
 <code>
 Set<V> edgesToQ = reverseAdjacencies.get(q);
if (edgesToQ == null) {
 edgesToQ = new HashSet<>();
 reverseAdjacencies.put(q, edgesToQ);
}
edgesToQ.add(p);

</code>
 </pre>
  
    现在删除节点
     <code>
 r
 </code>
    ，
  
   <pre>
 <code>
 // 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);

</code>
 </pre>
  
    我遗漏了像空检查这样的细节。
  
</DIV>