Введение
Абстрактный тип данных в информатике
В информатике граф — это абстрактный тип данных, предназначенный для реализации концепций неориентированного и ориентированного графов из области теории графов в математике. Структура данных графа состоит из конечного (и, возможно, изменяемого) множества вершин (также называемых узлами или точками) вместе с множеством неупорядоченных пар этих вершин для неориентированного графа или множеством упорядоченных пар для ориентированного графа. Эти пары известны как рёбра (также называемые связями или линиями), а для ориентированного графа также известны как рёбра, но иногда также как стрелки или дуги. Вершины могут быть частью структуры графа или внешними сущностями, представленными целочисленными индексами или ссылками. Структура данных графа может также ассоциировать с каждым ребром некоторое значение ребра, такое как символическая метка или числовой атрибут (стоимость, пропускная способность, длина и т. д.).
Более эффективное представление соседствующих множеств
Временная сложность операций в представлении списка смежности может быть улучшена за счет хранения множеств смежных вершин в более эффективных структурах данных, таких как хеш-таблицы или сбалансированные двоичные деревья поиска (последнее представление требует, чтобы вершины идентифицировались элементами линейно упорядоченного множества, например, целыми числами или строками символов). Использование хеш-таблиц для представления смежных вершин приводит к амортизированной средней временной сложности для проверки смежности двух заданных вершин и удаления ребра, а также к амортизированной средней временной сложности для удаления заданной вершины x степени d. Временная сложность остальных операций и асимптотические требования к памяти при этом не изменяются.
Параллельные представления
Параллелизация задач, связанных с графами, сталкивается со значительными трудностями: вычислениями, определяемыми данными, неструктурированностью задач, плохой локальностью и высоким отношением объема доступа к данным к объему вычислений. Представление графа, используемое для параллельных архитектур, играет важную роль в преодолении этих трудностей. Неудачно выбранные представления могут неоправданно увеличить стоимость коммуникаций алгоритма, что приведет к снижению его масштабируемости. Далее рассматриваются архитектуры с общей и распределенной памятью.
Общая память
В случае модели общей памяти, графические представления, используемые для параллельной обработки, остаются такими же, как и в последовательном случае, поскольку параллельный доступ только для чтения к графическому представлению (например, списку смежности) эффективен в общей памяти.
Распределенная память
В модели распределенной памяти обычный подход заключается в разбиении множества вершин графа на подмножества. Здесь – количество доступных элементов обработки (PE). Затем эти подмножества вершин распределяются по ПЭ с соответствующими индексами, а также по соответствующим ребрам. Каждый ПЭ имеет собственное представление подграфа, при этом ребрам, имеющим конечную точку в другом подмножестве, требуется особое внимание. Для стандартных интерфейсов связи, таких как MPI, необходимо идентифицировать ID ПЭ, владеющего другой конечной точкой. В процессе вычислений в распределенных алгоритмах обработки графов передача информации по этим ребрам подразумевает коммуникацию. Однако разбиение графа – это NP-трудная задача, поэтому вычислить оптимальное разбиение не представляется возможным. Вместо этого используются следующие эвристики. 1D-разбиение: каждый процессор получает вершин и соответствующие исходящие ребра. Это можно представить как разложение матрицы смежности по строкам или столбцам. Для алгоритмов, работающих с таким представлением, требуется шаг коммуникации "все-к-всем", а также буферы сообщений размера , поскольку каждый ПЭ потенциально может иметь исходящие ребра ко всем остальным ПЭ. 2D-разбиение: каждый процессор получает подматрицу матрицы смежности. Предположим, что процессоры расположены в виде прямоугольника , где и – количество элементов обработки в каждой строке и столбце соответственно. Тогда каждый процессор получает подматрицу матрицы смежности размерности , которую можно визуализировать как шахматную доску.
Ширина первого поиска и глубина первого поиска
Поиск в ширину (BFS) и поиск в глубину (DFS) — это два тесно связанных алгоритма, используемых для обхода всех узлов в заданном связном компоненте. Оба начинаются с произвольной вершины, называемой "корнем".