В информатике граф — это абстрактный тип данных , предназначенный для реализации концепций неориентированного графа и ориентированного графа из области теории графов в математике .
Структура данных графа состоит из конечного (и, возможно, изменяемого) набора вершин ( также называемых узлами или точками ), вместе с набором неупорядоченных пар этих вершин для неориентированного графа или набором упорядоченных пар для ориентированного графа. Эти пары известны как ребра (также называемые связями или линиями ), а для ориентированного графа также известны как ребра , но также иногда как стрелки или дуги . Вершины могут быть частью структуры графа или могут быть внешними сущностями, представленными целочисленными индексами или ссылками .
Структура данных графа может также связывать с каждым ребром некоторое значение ребра , например, символическую метку или числовой атрибут (стоимость, емкость, длина и т. д.).
Основные операции, предоставляемые структурой данных графа G , обычно включают: [1]
Структуры, связывающие значения с краями, обычно также обеспечивают: [1]
В следующей таблице приведены затраты времени на выполнение различных операций над графами для каждого из этих представлений, где | V | — число вершин, а | E | — число ребер. [ необходима цитата ] В матричных представлениях записи кодируют затраты на прохождение ребра. Затраты на отсутствующие ребра предполагаются равными ∞.
Списки смежности обычно предпочтительны для представления разреженных графов , в то время как матрица смежности предпочтительна, если граф плотный; то есть число ребер близко к числу вершин в квадрате, или если необходимо иметь возможность быстро найти, есть ли ребро, соединяющее две вершины. [5] [6]
Временную сложность операций в представлении списка смежности можно улучшить, сохраняя наборы смежных вершин в более эффективных структурах данных, таких как хэш-таблицы или сбалансированные двоичные деревья поиска (последнее представление требует, чтобы вершины были идентифицированы элементами линейно упорядоченного набора, такими как целые числа или строки символов). Представление смежных вершин с помощью хэш-таблиц приводит к амортизированной средней временной сложности для проверки смежности двух заданных вершин и удаления ребра и амортизированной средней временной сложности [7] для удаления заданной вершины x степени . Временная сложность других операций и асимптотические требования к пространству не изменяются.
Параллелизация графовых задач сталкивается со значительными трудностями: вычисления, управляемые данными, неструктурированные проблемы, плохая локальность и высокий коэффициент доступа к данным для вычислений. [8] [9] Представление графа, используемое для параллельных архитектур, играет важную роль в решении этих проблем. Плохо выбранные представления могут неоправданно повысить стоимость связи алгоритма, что снизит его масштабируемость . Далее рассматриваются архитектуры с общей и распределенной памятью.
В случае модели общей памяти представления графов, используемые для параллельной обработки, такие же, как и в последовательном случае, [10], поскольку параллельный доступ только для чтения к представлению графа (например, список смежности ) эффективен в общей памяти.
В модели распределенной памяти обычный подход заключается в разбиении набора вершин графа на множества . Здесь — количество доступных элементов обработки (PE). Разделы набора вершин затем распределяются по PE с соответствующим индексом, в дополнение к соответствующим ребрам. Каждый PE имеет свое собственное представление подграфа , где ребра с конечной точкой в другом разделе требуют особого внимания. Для стандартных интерфейсов связи, таких как MPI , идентификатор PE, владеющего другой конечной точкой, должен быть идентифицируемым. Во время вычислений в алгоритмах распределенного графа передача информации по этим ребрам подразумевает связь. [10]
Разделение графа должно быть выполнено аккуратно - есть компромисс между низкой коммуникацией и равномерным размером раздела [11] Но разделение графа является NP-трудной задачей, поэтому вычислить их не представляется возможным. Вместо этого используются следующие эвристики.
1D разбиение: Каждый процессор получает вершины и соответствующие исходящие ребра. Это можно понимать как разложение матрицы смежности по строкам или столбцам. Для алгоритмов, работающих с этим представлением, это требует шага связи All-to-All, а также размеров буфера сообщений, поскольку каждый PE потенциально имеет исходящие ребра к каждому другому PE. [12]
Двумерное разбиение: Каждый процессор получает подматрицу матрицы смежности. Предположим, что процессоры выровнены в прямоугольнике , где и — количество элементов обработки в каждой строке и столбце соответственно. Тогда каждый процессор получает подматрицу матрицы смежности размерности . Это можно визуализировать как шахматный узор в матрице. [12] Следовательно, каждый процессорный блок может иметь исходящие ребра только к PE в той же строке и столбце. Это ограничивает количество партнеров по коммуникации для каждого PE до возможных .
Графы с триллионами ребер встречаются в машинном обучении , анализе социальных сетей и других областях. Сжатые графовые представления были разработаны для снижения требований к вводу-выводу и памяти. Применимы общие методы, такие как кодирование Хаффмана , но список смежности или матрица смежности могут быть обработаны определенным образом для повышения эффективности. [13]
Поиск в ширину (BFS) и поиск в глубину (DFS) — это два тесно связанных подхода, которые используются для исследования всех узлов в заданном связанном компоненте . Оба начинаются с произвольного узла, « корня ». [14]