Алгоритм — Реализация разреженного графика & amp; Производительность в переполнении стека
В настоящее время я работаю над структурой данных ориентированного графа в C ++ (нет Boost GL для этого проекта). Основным приложением будет определение подключенных компонентов и приемников. Ожидается, что графики будут разреженными (верхний предел E ~ 4V на числовых ребрах) и будут иметь одинаковый вес. Я пытаюсь сделать выбор между списком смежности, списком инцидентов или, возможно, каким-либо другим представлением, о котором я еще не слышал (прил. Матрица не является опцией bc разреженности). Скорее всего, узким местом будет пространство в целом и скорость инициализации графа: графы будут инициализироваться из потенциально огромных массивов, так что каждый элемент в массиве в конечном итоге станет вершиной с направленным ребром к одному из соседних элементов. Чтобы получить ребра для каждой вершины, сначала нужно сравнить все соседние элементы.
Мои вопросы: (1) Какое представление обычно быстрее инициализировать, а также быстро для обхода BFS, (2) Какие алгоритмы (кроме ванильного BFS) существуют для поиска связанных компонентов? Я знаю, что это O (V + E) с использованием BFS (что, я думаю, является оптимальным), но меня беспокоит размер промежуточной очереди, поскольку ширина графика растет экспоненциально с высотой.
Не имею большого опыта в реализации графиков, поэтому буду благодарен за любые предложения.
Решение
Рассмотрим макет следующим образом:
Список смежности может быть реализован в виде массива [Nx4] (в данном случае n равно 3, а 4, потому что вы говорите, что 4 — максимальное число ребер в вашем случае) в следующей форме:
2 3 0 0
3 0 0 0
0 0 0 0
Приведенное выше представление предполагает, что количество вершин находится в отсортированном порядке, где первый индекс в массиве определяется как (v-1),
Список инцидентности, с другой стороны, требует, чтобы вы определили список вершин, список ребер и элементы соединения между ними (список заболеваемости — график).
Оба хороши с точки зрения использования пространства по сравнению с матрицей смежности, так как ваш граф, как вы сказали, очень разреженный.
Мое предложение состоит в том, чтобы пойти со списком смежности, который вы можете инициализировать как непрерывный массив [Nx4] в памяти (так как вы говорите, что у вас будет максимум 4 ребра для одной вершины). Это представление будет быстрее инициализироваться. (Кроме того, это представление будет работать лучше с точки зрения эффективности кэша.)
Однако, если вы ожидаете, что размер вашего графика будет изменяться динамически и часто, списки заболеваемости могут быть лучше, поскольку они обычно реализуются как списки, которые не являются смежными пробелами (см. Ссылку выше). Перераспределение и выделение массива смежности может быть нежелательным в этом случае.
Другие решения
Вероятно, наиболее эффективным способом реализации графа для ваших целей является сочетание списка смежности для каждой вершины и дополнительно хеширующей структуры, которая отображает пары вершин на ребра, если таковые существуют. Для этого потребуется пространство O (| V | + | E |) для списка смежности, O (| E |) для структуры хеширования и даст вам ожидаемое O (1) containsEdge(vertex v, vertex w), insertEdge(vertex v, vertex w) а также removeEdge(vertex v, vertex w) с помощью сопоставления получить указатели, необходимые для быстрого изменения списков смежности вершин.
Матрица Смежности хороша для плотных графов, они оказываются плохим выбором для больших разреженных графов. Вот временные и пространственные сложности простых операций для разреженных графов.
Разреженный граф Big O Временные и пространственные сложности
Рассмотрим среднее количество ребер менее 4 для графа 1 миллион узлов. Большинство современных компьютеров не в состоянии содержать матрицу смежности, учитывая их пространственную сложность O (n * n), т. Е. Потребность в ОЗУ в несколько ТБ. Принимая во внимание, что он может легко поместиться в недорогой ноутбук с базовой конфигурацией с требованием оперативной памяти в несколько МБ.