хранение графа с неизвестным порядком узлов

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]]

.

EDIT:
Второй возможностью будет использование set вместо vector для хранения элементов, но это может быть не всегда желательно [set не имеет дубликатов и не будет содержать элементы в порядке их вставки], но подумайте, подходит ли вам это.