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

Question

我需要存储一个有向图（不一定是无环的），以便节点删除尽可能快速。为了知道在删除节点时哪些边需要去掉，我不介意存储额外的数据。

如果我存储边的列表（作为节点索引对），那么当删除某个节点n时，我必须搜索整个列表以查找其源或目标为n的边。这对我的应用程序来说太昂贵了。是否可以通过在节点中存储一些附加数据来避免此搜索？

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

能否避免这种情况发生呢？

谢谢。

- Amenhotep

---

每个顶点通常会有多少条边？如果顶点度数较低，特别是如果邻接列表按某种顶点 ID 进行排序以允许二进制搜索，则您建议的邻接列表搜索可能不会太昂贵。请记住，由于已删除的顶点自身的源和目标列表，您将知道任何给定顶点的所有相邻顶点。 - Jeremiah Willcock

通常，一个顶点有大约10-30条入边和5-10条出边。但是有一些顶点可能有数百个出边。保持邻接列表排序的想法可能行得通…尽管这意味着我必须花时间在创建新顶点时对那些列表进行排序。 - Amenhotep

Answer 1

你有两种选择，不需要太复杂，分别是邻接表和邻接矩阵。对于你所做的事情，前者可能是最好的选择。要删除一个节点，只需消除所有出边的节点列表即可。对于入边，你可以考虑为每个列表保留哈希表以进行O(1)查找。

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

- dfb

---

是的，邻接表看起来更好（尽管高效的稀疏矩阵算法也可能有效）。与哈希表不同，Trie树会更好吗？Verdy_p在这篇帖子中建议如此... - Amenhotep

我从未听说过tries被用于这种方式，我很难理解链接中的帖子在指什么。如果您有原始来源的链接，我很感兴趣去看看。 - dfb

不，我也不知道。我只是想寻找如何优化搜索。 - Amenhotep

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.
  }

}

基本上，每条边用两个互相交叉的插槽来表示。每个顶点都有一个这样的插槽列表。

当一个顶点被删除时，它会递归地向上发送“kill”信号到其插槽列表。每个插槽会响应并销毁其另一端（从邻居列表中优雅地弹出，修补其后面的prev/next指针）。

这样，一个顶点以及其所有边都可以在不搜索任何内容的情况下被删除。我需要付出的代价是内存：与常规双向链接邻接表的3个指针（prev、next和vertex）相比，我必须保留4个指针（prev、next、vertex和other_end）。

这就是基本思想。对于有向图，我只需要在IN插槽和OUT插槽之间进行区分。可能通过将每个顶点的邻接列表分成两个单独的列表：IN_slot_list和OUT_slot_list来实现。

- Amenhotep

---

这个例子使用了什么编程语言？看起来像是Java，这是正确的吗？ - Anderson Green