有向图的数据结构，允许快速删除节点？

Question

我需要存储有向图（不一定是非循环的），以便节点删除尽可能快。我不介意存储额外的数据，以便准确地知道删除节点时必须删除哪些边。

如果我存储一个边列表（作为节点索引对），那么当杀死某个节点 n 时，我必须在整个列表中搜索源或目标为 n 的边。这对于我的应用来说成本太高了。是否可以通过在节点中存储一些附加数据来避免这种搜索？

一种想法是让每个节点将其自己的源和目标存储为两个单独的列表。当节点 n 被杀死时，它的列表也被杀死。但是，链接到节点 n 的所有目标/源如何知道更新它们自己的列表（即，从它们的列表中消除失效的节点）？这将需要一些昂贵的搜索......

可以避免吗？

谢谢。

Answer 1

您有两个选择，但不会太花哨：邻接列表和邻接矩阵。前者可能最适合您正在做的事情。要删除节点，只需删除该节点的列表中的所有出边即可。对于入边，您可以考虑为每个列表保留一个哈希表以进行 O(1) 查找。

这是一个很好的概述
http://www.algorithmist.com/index.php/Graph_data_structs

Answer 2

我解决了！这是无向图的解决方案，之后添加方向很容易。

在每个顶点中我保留一个特殊的邻接列表。它是一个列表（双链接，以便于插入/删除），其元素是“槽”：

class Slot {
  Slot prev, next; // pointers to the other slots in the list
  Slot other_end; // the other end of the edge: not a vertex, but a Slot!
  Vertex other_vertex; // the actual vertex at the other end

  void kill() {
    if (next!=null) next.kill(); // recursion
    other_end.pop_out();
  }

  void pop_out() {
    if (next!=null) next.prev = prev;
    if (prev!=null) prev.next = next;
    else other_end.other_vertex.slot_list = next; // in case this slot is the
                                                  // first in its list, I need
                                                  // to adjust the vertex's
                                                  // slot_list pointer.
    // other_end.other_vertex is actually the vertex to which this slot belongs;
    // but this slot doesn't know it, so I have to go around like this.
  }

}

因此基本上每条边都由两个槽表示，彼此交叉。每个顶点都有一个此类插槽的列表。

当一个顶点被杀死时，它会在其槽列表中递归地发送“杀死”信号。每个槽通过销毁其 other_end 来响应（它慷慨地从邻居列表中弹出，修复后面的上一个/下一个指针）。

这样，无需任何搜索即可删除顶点及其所有边。我必须付出的代价是内存：我必须保留 4 个指针（prev、next、vertex 和 other_end），而不是 3 个指针（常规双链接邻接表的 prev、next 和 vertex）。

这是基本思想。对于有向图，我只需要以某种方式区分 IN 槽和 OUT 槽。可能通过将每个顶点的邻接列表划分为两个单独的列表：IN_slot_list 和 OUT_slot_list。