关于添加和删除

Question

老师，想问一下，矩阵和列表都是基于节点的索引来实现的。也就是说所有节点的数据都存在一个数组里面。
那添加一个节点或者删除一个节点，是不是要维护这个节点索引呢？比如删除一个节点，那么它后面的所有节点的索引都要减一。
能帮忙提供一个简单的思路吗？

Answer 1

liuyubobobo 2019-08-23 00:35:21

抱歉，我没有理解你的问题，你说的“矩阵和列表”，具体是指什么数据结构？

==========

首先，是的，有很多图算法，不会涉及删除节点的问题。

其次，删除节点的需求确实也是存在的。其实最简单的思路，是做一个掩码。比如有一个数组del，del[i]=true 表示节点i被删除了。之后，对于图的所有操作（主要是遍历相邻接点），看到节点i，就忽略就好了，因为这个i已经被删除了。这个思路适于少量删除节点的情况。

如果图结构的节点动态性非常强的话，应该使用邻接表。同时，整个表组织成一个哈希表或者红黑树。用C++的语言的话，图结构应该是：

unordered_map<int, unordered_map<int>>

即，哈希表中存储的键-值数据对，是每一个int，表示顶点序号，对应一个容器unordered_map<int>，表示和这个顶点相邻的顶点。这个数据结构可以保证能够快速删除某一个顶点。复杂度是O(n)的。

但是，是的，键也不连续了。但在这种情况下，因为有删除，我们也不需要维护连续性。一个图可有0，2，3，5，7 这样的5个顶点，而不是0，1，2，3，4：）

继续加油！：）

• 提问者 ForsunFor #1

  抱歉，我没有说清楚
  图这种数据结构，不管是邻接矩阵还是邻接表来表示，它所表示的都是索引为 x 的节点和索引为 y 的节点相连接。
  如果我要存储的每个节点都是一个对象，里面包含很多信息，那么就需要一个数组，把这些对象都存储起来，数组的键就是这些节点的索引值。然后再用图的邻接矩阵或者邻接表把这些节点都连接起来成为一张图。
  我的问题是，如果我要删除图中的一个节点，不光要把这张表的邻接表或者邻接矩阵中对应的节点索引信息删除，维护这个图中节点索引的这个数组，也要删除对应的键。
  删除之后不管是邻接表还是邻接矩阵，还是记录数据的索引数组，其中的键都不连续了。
  有什么办法来处理这个删除图中的节点之后，维护这个图的数组键不连续的问题吗?
  或者是图的这种数据结构，很少作删除节点这个操作？

• liuyubobobo 回复 提问者 ForsunFor #2

  我补充在原回答里了：）

• 提问者 ForsunFor #3

  非常感谢！