Я ищу эффективный способ реализации взвешенного неориентированного графа, заранее зная только количество ребер.
образец ввода:
N (количество ребер)
A B x (x — расстояние от A до B)
.
.
Я думал использовать списки смежности Node* (мне нужно знать соседей) и сохраненные узлы в динамической хеш-таблице (я не знаю, сколько узлов я возьму, поэтому мне нужен динамический - поиск/вставка - контейнер ).
Есть ли лучшие способы сделать это?
Извините за мой плохой английский! :D
Учитывая формат, в котором вы получаете ввод, очень разумным подходом было бы использование либо хеш-таблицы списков, где ключи — это узлы, а значения — списки пар (узел, расстояние). В качестве альтернативы, если у вас есть плотный граф и вы хотите иметь возможность быстро определить расстояние от одного узла до другого, может быть хорошо иметь хеш-таблицу хэш-таблиц, где хэш-таблица верхнего уровня отображает узлы во вторую хэш-таблицу. , который затем сопоставляет каждый узел исходного узла с его стоимостью. Это по-прежнему позволяет вам перебирать исходящие ребра узла, но дает вам более быстрый поиск расстояний.
Другая идея (в зависимости от варианта использования) состоит в том, чтобы начать с построения первой структуры данных (хеш-таблицы списков), а затем обработать ее, построив матрицу смежности. Это было бы полезно, если бы вам не нужно было перебирать исходящие ребра узла и требовался быстрый произвольный доступ к расстояниям между узлами. Она похожа на хеш-таблицу хэш-таблиц, но, вероятно, более эффективна в пространстве.
Надеюсь это поможет!
