Как реализовать минимальное связующее дерево в C++ с более чем 2000 узлами?

Question

Я хочу найти MST графа, который имеет более 2000 узлов. Проблема, которую я получаю, заключается в том, что я не могу сделать матрицу смежности размером более 1500X1500 (если размер больше, чем эта ошибка сегментации, потому что мы можем создать массив размером не более 10^7). Как это можно сделать?

Answer 1

Существует множество проблем, о которых стоит подумать.

1. Вы должны быть в состоянии выделить массив размером 1500 × 1500, не вызывая Segfault, при условии, что вы делаете это правильно. Если вы попытаетесь выделить массив такого размера в стеке (то есть, как локальную переменную), то вы, вероятно, продублите пространство стека, что, скорее всего, вызывает ошибку, которую вы получаете. Однако, если вы выделите его с помощью new[] или с помощью std::vector, тогда память будет храниться в куче, которая предназначена для размещения таких запросов.

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