algorithm - 存储具有未知节点顺序的图

Question

在向量中存储节点顺序未知的图形的最佳方法是什么。例如，我有节点以未知顺序出现，如 35、23、89、200、12、89、569 等......我想以这样一种方式存储它们，即不浪费内存并且如果在恒定时间内有效地访问节点然后这将会非常棒。可能有些哈希函数会起作用，但如果有一个可以区分节点的函数，请告诉我，或者是否有任何其他方法。

谢谢

Answer 1

我想到的最简单的解决方案就是按顺序将它们插入到您的向量中，然后创建一个 map<int,int>从它们的值映射到它们的索引。

在你的例子中:

map[35] == 0
ma[[23] == 1
map[89] == 2
map[200] == 3
map[12] == 4
...

现在，访问节点i作为vector[map[i]]

编辑:
第二种可能是使用set。而不是 vector保存元素，但它可能并不总是需要的 [set 没有重复项，并且不会按照您插入的顺序包含元素]，但请考虑它是否适合您。