插入并迅速

Question

什么是最好的数据结构做如下操作快速

• 插入
• 查找搜索。

感谢 阿维纳什

Answer 1

图邻接列表的一个好实现是使用动态分配的整数向量。

假设您的图中至多有N个节点。您可以将图存储在一个由N个动态分配的整数向量组成的数组中。 它看起来像这样：

矢量[N]

从节点x插入一个边缘节点Y使用：

矢量[X] .push（Y）

这如果图很稀疏（没有很多边），可以快速找到节点的所有输出边。

如果您想查找x和y之间是否存在边，则必须通过vector [x]并搜索它。如果你想加快速度，那么如果节点数很少（小于1000是合理的），你可以使用2维布尔数组。

如果你有很多节点并且想要加速这个操作，你可以使用散列表。

Answer 2

根据我的hash_map

Answer 3

如果相同的数据结构需要做两个业务，那么它应该是一个hash map。