Подходящая структура данных для больших графиков

У меня есть большой граф, есть ли какая-либо другая структура данных, кроме списка смежности и «матрицы смежности»? в c ++ stl или какой-либо другой структуре данных, которую я могу использовать для такого большого графа, фактически матрица смежности моего графа не помещается в основную память. Мой график направлен, и я реализую алгоритм Дейкстры в C ++.

Я видел предыдущие посты ... но я ищу подходящую структуру данных относительно dijkstra.

Под большим я подразумеваю граф, содержащий более 100 миллионов узлов и ребер.

 David Brabant29 мая 2012 г., 14:59
Определите «большой».
 Mr.Anubis29 мая 2012 г., 15:09
Есть ли граф граф уже в Boost
 user135451029 мая 2012 г., 15:02
@DavidBrabant Спасибо за ответ .. Я определил
 Hindol15 июл. 2012 г., 13:58
@ Mr.Anubis Да, но использовать его исключительно сложно.

Ответы на вопрос(1)

Обычно представляются списки смежности в виде списков целых чисел, где целое число является индексом узла. Как насчет большей эффективности использования пространства, вместо этого рассматривая список смежности как битовую строку00010111000... где1 в n-й позиции представляет ребро между этим узлом и узломn? Затем сожмите цепочку битов по некоторому стандартному алгоритму; распакуйте его, как вам нужно. Битовые строки, вероятно, будут сжиматься довольно хорошо, так что это меняет эффективность пространства для более высоких вычислительных затрат.

 29 мая 2012 г., 16:27
это то же самое, что матрица смежности, ..
 user135451029 мая 2012 г., 17:16
Я..это то же самое, что матрица смежности
 29 мая 2012 г., 16:09
Неплохая идея! Мне может понадобиться использовать это в какой-то момент :). Если он использует C ++, тоstd::bitset может работать лучше

Ваш ответ на вопрос