Эффективный способ отображения графиков

Question

Я изучал графики в университете (как часть Discreet Math, так и в классе структуры данных). Два способа представления графов есть то плюсы и минусы следующим образом:

1. , используя матрицу для представления графа: O(1) времени, чтобы проверить, если подключены два узла, O(n) времени извлечения случайного узла, подключенный к определенному узлу.
2. с использованием списка для представления графика: O(1) для извлечения случайного узла, подключенного к определенному узлу (если есть), O(n), чтобы проверить, связаны ли узлы i и j.

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

Матрица состоит только из 0 и 1. Итак, давайте вводим строки кода в двоичные строки и в десятичные. Теперь у нас будет массив ints, где array[i] представляет узел i. Получение случайного узла, подключенного к узлу i, тривиально и имеет O(1). Теперь, если узел i подключен к узлу j, это вызывает сомнения. Теперь нам нужно array[i] (будучи int в базе 10) конвертировать в двоичный файл и проверить, есть ли 1 на i-м месте в двоичной строке. Это делается O(log n).

Мой вопрос: существуют ли еще более эффективные способы получения этого результата? Что вы думаете о моей идее?

Answer 1

Сложные методы приближения матрицы к списку, которые вы указываете в начале, являются правильными. Однако:

Я думаю array[i] в вашей нотации это причудливый способ сказать «в i-й строке матрицы, за исключением того, что это битовый», который не изменяет выполнения сложности любых из алгоритмов. Почему извлекается случайный узел, подключенный к узлу, соответствующий array[i] «тривиальный»? Он по-прежнему O(n). Имейте в виду также, что если ваш граф имеет более 32, 64, любое количество вершин, вам нужен массив, состоящий из чего-то большего, чем int s.

Проверка, если есть в i-м месте в int1 является O(1). Вы правы в том, что сложность поиска случайного соседа array[i] возрастает, если у вас есть члены данных произвольной точности, составляющие array (как вам, вероятно, понадобится), но он достигает O(n), а не O(log n).

Редактировать: Я ошибся; с вашим представлением array (хотя обратите внимание, что это точно не определено), проверяя, являются ли два узла соседними: O(1). Вам не нужно «преобразовывать в двоичный», потому что компьютер хранит данные в двоичной форме изначально: вы просто описываете использование битового поля, а проверка i-го бита битового поля - O(1).