График (абстрактный тип данных)

Ориентированный граф с тремя вершинами (синие кружки) и тремя ребрами (черные стрелки).

В информатике граф , — это абстрактный тип данных который предназначен для реализации понятий неориентированного графа и ориентированного графа из области теории графов в математике .

Структура данных графа состоит из конечного (и, возможно, изменяемого) ( также набора вершин называемого узлами или точками ) вместе с набором неупорядоченных пар этих вершин для неориентированного графа или набора упорядоченных пар для ориентированного графа. Эти пары известны как ребра (также называемые ссылками или линиями ), а для ориентированного графа они также известны как ребра , а иногда и как стрелки или дуги . Вершины могут быть частью структуры графа или внешними объектами, представленными целочисленными индексами или ссылками .

Структура данных графа также может ассоциировать с каждым ребром некоторое значение ребра , например символическую метку или числовой атрибут (стоимость, емкость, длина и т. д.).

Операции

UML class diagram of a Graph (abstract data type)

Основные операции, предоставляемые структурой данных графа G , обычно включают в себя:

• смежный( G , x , y ) : проверяет, есть ли ребро от вершины x до вершины y ;
• соседи( G , x ) : перечисляет все вершины y такие, что существует ребро от вершины x до вершины y ;
• add_vertex( G , x ) : добавляет вершину x , если ее там нет;
• Remove_vertex( G , x ) : удаляет вершину x , если она там есть;
• add_edge( G , x , y , z ) : добавляет ребро z из вершины x в вершину y , если его там нет;
• Remove_edge( G , x , y ) : удаляет ребро из вершины x в вершину y , если оно там есть;
• get_vertex_value( G , x ) : возвращает значение, связанное с вершиной x ;
• set_vertex_value( G , x , v ) : устанавливает значение, связанное с вершиной x, в значение v .

Структуры, которые связывают значения с краями, обычно также обеспечивают:

• get_edge_value( G , x , y ) : возвращает значение, связанное с краем ( x , y );
• set_edge_value( G , x , y , v ) : устанавливает значение, связанное с ребром ( x , y ), равным v .

Общие структуры данных для графического представления

Список смежности

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

Матрица смежности

Двумерная матрица, в которой строки представляют исходные вершины, а столбцы — конечные вершины. Данные о ребрах и вершинах должны храниться снаружи. Между каждой парой вершин можно хранить только стоимость одного ребра.

Матрица заболеваемости

Двумерная матрица, в которой строки представляют вершины, а столбцы — ребра. Записи указывают отношение инцидентности между вершиной в строке и ребром в столбце.

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

	Список смежности	Матрица смежности	Матрица заболеваемости
График магазина	$O(|V|+|E|)$	$O(|V|^{2})$	$O(|V|\cdot |E|)$
Добавить вершину	$O(1)$	$O(|V|^{2})$	$O(|V|\cdot |E|)$
Добавить край	$O(1)$	$O(1)$	$O(|V|\cdot |E|)$
Удалить вершину	$O(|E|)$	$O(|V|^{2})$	$O(|V|\cdot |E|)$
Удалить край	$O(|V|)$	$O(1)$	$O(|V|\cdot |E|)$
Являются ли вершины x и y смежными (при условии, что места их хранения известны)?	$O(|V|)$	$O(1)$	$O(|E|)$
Примечания	Медленно удалять вершины и ребра, поскольку необходимо найти все вершины или ребра.	Медленно добавлять или удалять вершины, поскольку необходимо изменить размер/скопировать матрицу.	Медленно добавлять или удалять вершины и ребра, поскольку необходимо изменить размер/копировать матрицу.

Списки смежности обычно предпочтительны для представления разреженных графов , тогда как матрица смежности предпочтительна, если граф плотный; то есть количество ребер $|E|$ близко к числу вершин в квадрате, $|V|^{2}$, или если нужно иметь возможность быстро найти, есть ли ребро, соединяющее две вершины.

Более эффективное представление наборов смежности

Временную сложность операций в представлении списка смежности можно улучшить за счет хранения наборов соседних вершин в более эффективных структурах данных, таких как хеш-таблицы или сбалансированные двоичные деревья поиска (последнее представление требует, чтобы вершины идентифицировались элементами линейно упорядоченного списка). набор, например целые числа или строки символов). Представление соседних вершин через хеш-таблицы приводит к амортизированной средней временной сложности $O(1)$ проверить смежность двух заданных вершин и удалить ребро и амортизированную среднюю временную сложность из $O(\deg(x))$ удалить данную вершину x степени $\deg(x)$. Временная сложность других операций и требования к асимптотическому пространству не меняются.

Параллельные представления

Распараллеливание задач на графах сталкивается с серьезными проблемами: вычисления, управляемые данными, неструктурированные проблемы, плохая локальность и высокое соотношение доступа к данным и вычислений. Представление в виде графа, используемое для параллельных архитектур, играет важную роль в решении этих проблем. Плохо выбранные представления могут неоправданно увеличить стоимость связи алгоритма, что снизит его масштабируемость . Далее рассматриваются архитектуры с общей и распределенной памятью.

Общая память

В случае модели с общей памятью графовые представления, используемые для параллельной обработки, такие же, как и в последовательном случае. поскольку параллельный доступ только для чтения к представлению графа (например, списку смежности ) эффективен в общей памяти.

Распределенная память

В модели распределенной памяти обычным подходом является разделение набора вершин. $V$ графа в $p$ наборы $V_{0},\dots ,V_{p-1}$. Здесь, $p$– количество доступных обрабатывающих элементов (ПЭ). Разделы набора вершин затем распределяются по PE с совпадающим индексом, а также по соответствующим ребрам. Каждый PE имеет свое собственное представление подграфа , где ребра с конечной точкой в ​​другом разделе требуют особого внимания. Для стандартных интерфейсов связи, таких как MPI , идентификатор PE, владеющего другой конечной точкой, должен быть идентифицируемым. Во время вычислений в алгоритмах распределенного графа передача информации по этим ребрам подразумевает связь.

Разделение графа необходимо выполнять осторожно — существует компромисс между низким уровнем взаимодействия и равномерным разделением по размеру. Но разбиение графа является NP-сложной задачей, поэтому вычислить их невозможно. Вместо этого используются следующие эвристики.

1D-разделение: каждый процессор получает $n/p$вершины и соответствующие им исходящие ребра. Это можно понимать как разложение матрицы смежности по строкам или по столбцам. Для алгоритмов, работающих с этим представлением, это требует шага связи «все-ко-всем», а также ${\mathcal {O}}(m)$ размеры буфера сообщений, поскольку каждый PE потенциально имеет исходящие ребра к каждому другому PE.

2D-разделение: каждый процессор получает подматрицу матрицы смежности. Предположим, что процессоры выровнены в прямоугольнике. $p=p_{r}\times p_{c}$, где $p_{r}$ и $p_{c}$— количество обрабатывающих элементов в каждой строке и столбце соответственно. Затем каждый процессор получает подматрицу матрицы смежности размерности $(n/p_{r})\times (n/p_{c})$. Это можно представить в виде шахматной доски в матрице. Следовательно, каждый процессор может иметь исходящие ребра к PE только в одной строке и столбце. Это ограничивает количество коммуникационных партнеров для каждого PE до $p_{r}+p_{c}-1$ снаружи $p=p_{r}\times p_{c}$ возможные.

Сжатые представления

Графы с триллионами ребер встречаются в машинном обучении , анализе социальных сетей и других областях. Сжатые графические представления были разработаны для уменьшения требований к вводу-выводу и памяти. общие методы, такие как кодирование Хаффмана , но список смежности или матрица смежности могут обрабатываться особыми способами для повышения эффективности. Применимы

Обход графа

Поиск в ширину и поиск в глубину

Поиск в ширину (BFS) и поиск в глубину (DFS) — это два тесно связанных подхода, которые используются для исследования всех узлов в данном связном компоненте . Оба начинаются с произвольного узла, « корня ».

См. также

• Обход графа для получения дополнительной информации о стратегиях обхода графа
• База данных графов для постоянства графов (структур данных)
• Переписывание графов для преобразований графов (структур данных графов) на основе правил.
• Программное обеспечение для рисования графиков для программного обеспечения, систем и поставщиков систем для рисования графиков

Внешние ссылки

• Boost Graph Library: мощная библиотека графов C++ sa Boost (библиотеки C++)
• Networkx: графовая библиотека Python.
• GraphMatcher — Java-программа для выравнивания направленных и неориентированных графиков.
• GraphBLAS Спецификация библиотечного интерфейса для операций с графами, с особым упором на разреженные графы.