C ++ оптимальное представление графа для алгоритма простых чисел (без форсирования)

Я ищу хорошее представление графика для алгоритма Прима.

например представлять график для BFS

typedef std::unordered_map<int, std::queue<int> > gr;

элегантный и лаконичный, он сопоставляет каждую вершину с очередью соседей.

Для Дейкстры это немного сложнее (вес в представлении)

typedef std::pair<int, double> to_weighted_edge;
typedef std::unordered_map<int, std::vector<to_weighted_edge> > gr;

• использование очереди приоритетов.

Если подобная структура должна следовать в алгоритме Прима, однако, источник каждого ребра также должен быть сохранен, и если график представлен следующим образом:

typedef std::pair < std::pair<int,int>, double> from_to_weighted_edge;
typedef std::unordered_map<int, std::vector<from_to_weighted_edge> > gr;

затем сохраняется избыточная информация (источник / из вершины).

Любые предложения о том, что было бы оптимальным представлением графа в C ++ для алгоритма Прима, приветствуются!

PS: конечно, можно представить граф как std::vector<from_to_weighted_edge> но тогда не будет O (1) поиска соседей, что является общей характеристикой всех общих представлений графов.