1回答

liuyubobobo

2019-08-23

已采纳

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

==========

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

其次，删除节点的需求确实也是存在的。其实最简单的思路，是做一个掩码。比如有一个数组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：）

继续加油！：）

1

3

ForsunFor

非常感谢！

2019-08-28

共3条回复