Вопрос по c, dijkstra, visual-c++, c++ – Подходящая структура данных для больших графиков

3

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

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

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

Есть ли граф граф уже в Boost Mr.Anubis
@ Mr.Anubis Да, но использовать его исключительно сложно. Hindol
Определите «большой». David Brabant
@DavidBrabant Спасибо за ответ .. Я определил user1354510

Ваш Ответ

1   ответ
2

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

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

Похожие вопросы