Как хранить этот вид графика?

Question

Предположим, у нас есть график с двунаправленными ребрами, без весов. Как я могу сохранить его, чтобы не тратить впустую тонны памяти, сделать его быстрым и иметь быстрый доступ к соседям каждой вершины? Я имею в виду, до сих пор для sth, как это: {(1,2)(1,5)(1,3)(2,4)(2,3)} Я использовал массив: array[1][2]=1 означает, что есть связь между 1 и 2. Есть две проблемы с этим:

• a) поскольку график является двунаправленным, (1,2) означает, что (2,1) также существует. Если я хочу иметь легкий доступ к соседям 2 позже, я должен сделать два изменения за итерацию: array[1][2]=1, array[2][1]=1

• b) когда я знаю, что в какой-то вершине (скажем, 5) остался только один сосед, мне приходится искать во всем array[5][x], проверяя все возможные x

• в) для графа из миллиона вершин этот монстр становится слишком обширным, чтобы его можно было использовать в любом соревновании

Не могли бы вы помочь мне и указать решение моих проблем?

Answer 1

Похоже, вы хотите карту наборов.

std::map< int, std::set< int > >

Так что для int вы можете хранить коллекцию всех своих соседей в наборе. Вам понадобятся функции для управления этой коллекцией.

Если число узлов исчисляемо, то есть они варьируются от 0 до N и включают все эти числа, тогда вы можете использовать std::vector< std::set<int> >, и это будет более эффективно. Вы также можете использовать std::vector< std::bitset<N> > или std::vector< boost::dynamic_bitset > >, если у вас есть, скажем, 20 000 узлов и, следовательно, вы можете предоставить 20 000 наборов битов по 2500 байт (плюс немного служебной информации) каждый = 50 МБ памяти (приблизительно).

Это немного более компактная модель, чем у вас, но не намного. Если у вас есть миллион вершин, это будет около 125 ГБ, поэтому, очевидно, вы не можете использовать эту модель, но должны использовать набор. Кроме того, итерация по вершине, чтобы увидеть ее соседей, - это гораздо более быстрая операция с набором, чем с набором битов.

Если не существует много вершин, в которых вообще нет соседей, и если они последовательно пронумерованы, карта не имеет преимуществ перед вектором.

Не уверен, сколько памяти вы называете "тоннами". Модель, которую я только что описал, использует постоянную память, в то время как карта наборов использует память, пропорциональную количеству отношений соседства, которые у вас есть, но по мере заполнения она будет гораздо менее компактной, чем вектор битовых наборов, поэтому будет потреблять больше.

Answer 2

Вы можете использовать треугольную матрицу.Это означает, что, скажем, если x

См.http://www.codeguru.com/cpp/cpp/algorithms/general/article.php/c11211 и https://stackoverflow.com/questions/8305186/isolating-triangle-array-items-and-evaluating-them-for-equality-then-outputting для примеров.