Создание графа на основе массива с помощью Java

Question

Мне нужно сгенерировать график с использованием целочисленных массивов.Края графиков сохраняются как ребра [e] [2], где e - количество ребер.Мне нужно, чтобы мой граф был связан, то есть вы должны иметь возможность проходить от всех узлов ко всем узлам.

dge [0] = {0,5} означает, что ребро соединяет узел 0 и узел 5. Не могли бы выпредложите алгоритм, пожалуйста?

И имейте в виду, что я буду генерировать графы с миллионами узлов, так что было бы лучше, если сложность алгоритма не слишком высока.

Answer 1

Если каждый узел напрямую связан с каждым узлом, не храните все ребра;)

Если каждый узел доступен из каждого другого узла, но не обязательно напрямую, используйте матрицу смежности .Это самый простой способ, если вам нужно использовать целочисленные массивы.

Если бы матрица была разреженной, я бы сохранил ее иначе.Наилучшее кодирование зависит от того, для каких графовых алгоритмов вы хотите его использовать. В статье Википедии о разреженных матрицах ) перечислены основные из них.