stringtranslate.com

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

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

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

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

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

Операции

Диаграмма классов UML для графа (абстрактный тип данных)
Диаграмма классов UML для графа (абстрактный тип данных)

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

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

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

Список смежности [2]
Вершины хранятся как записи или объекты, и каждая вершина хранит список смежных вершин. Эта структура данных позволяет хранить дополнительные данные о вершинах. Дополнительные данные могут храниться, если ребра также хранятся как объекты, в этом случае каждая вершина хранит свои инцидентные ребра, а каждое ребро хранит свои инцидентные вершины.
Матрица смежности [3]
Двумерная матрица, в которой строки представляют исходные вершины, а столбцы — конечные вершины. Данные о ребрах и вершинах должны храниться снаружи. Между каждой парой вершин может храниться только стоимость одного ребра.
Матрица инцидентности [4]
Двумерная матрица, в которой строки представляют вершины, а столбцы — ребра. Записи указывают отношение инцидентности между вершиной в строке и ребром в столбце.

В следующей таблице приведены затраты времени на выполнение различных операций над графами для каждого из этих представлений, где | 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]

Смотрите также

Ссылки

  1. ^ ab См., например, Goodrich & Tamassia (2015), Раздел 13.1.2: Операции над графами, стр. 360. Более подробный набор операций см. в Mehlhorn, K. ; Näher, S. (1999). "Глава 6: Графы и их структуры данных". LEDA: Платформа для комбинаторных и геометрических вычислений (PDF) . Cambridge University Press. стр. 240–282.
  2. ^ Кормен и др. (2001), стр. 528–529; Гудрич и Тамассия (2015), стр. 361–362.
  3. ^ Кормен и др. (2001), стр. 529–530; Гудрич и Тамассия (2015), с. 363.
  4. ^ Кормен и др. (2001), Упражнение 22.1-7, стр. 531.
  5. ^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л.; Стайн , Клиффорд (2001). «Раздел 22.1: Представления графов». Введение в алгоритмы (Второе изд.). MIT Press и McGraw-Hill. стр. 527–531. ISBN 0-262-03293-7.
  6. ^ Гудрич, Майкл Т .; Тамассиа, Роберто (2015). «Раздел 13.1: Терминология и представления графов». Разработка и применение алгоритмов . Wiley. С. 355–364. ISBN 978-1-118-33591-8.
  7. ^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л.; Стайн , Клиффорд (2009). Введение в алгоритмы (3-е изд.). Массачусетский технологический институт. С. 253–280. ISBN  978-0-262-03384-8.
  8. ^ Бадер, Дэвид; Мейерхенке, Хеннинг; Сандерс, Питер; Вагнер, Доротея (январь 2013 г.). Разбиение графов и кластеризация графов. Contemporary Mathematics. Том 588. Американское математическое общество. doi :10.1090/conm/588/11709. ISBN 978-0-8218-9038-7.
  9. ^ Ламсдейн, Эндрю; Грегор, Дуглас; Хендриксон, Брюс; Берри, Джонатан (март 2007 г.). «Проблемы параллельной обработки графов». Parallel Processing Letters . 17 (1): 5–20. doi :10.1142/s0129626407002843. ISSN  0129-6264.
  10. ^ ab Сандерс, Питер; Мельхорн, Курт; Дицфельбингер, Мартин; Дементьев, Роман (2019). Последовательные и параллельные алгоритмы и структуры данных: базовый набор инструментов. Springer International Publishing. ISBN 978-3-030-25208-3.
  11. ^ "Параллельная обработка графов" (PDF) . Архивировано из оригинала (PDF) 2021-08-25 . Получено 2020-03-09 .
  12. ^ ab Buluç, A.; Madduri, Kamesh (2011). "Applications". Параллельный поиск в ширину в системах с распределенной памятью . Международная конференция по высокопроизводительным вычислениям, сетевым технологиям, хранению и анализу 2011 года. CiteSeerX 10.1.1.767.5248 . doi :10.1145/2063384.2063471. ISBN  978-1-4503-0771-0. S2CID  6540738.
  13. ^ Беста, Мачей; Хёфлер, Торстен (27 апреля 2019 г.). «Обзор и таксономия сжатия графов без потерь и представления графов с эффективным использованием пространства». arXiv : 1806.01799 [cs.DS].
  14. ^ Purti (июль–сентябрь 2018 г.). «Обходы графов и их применение» (PDF) . Международный журнал исследований и аналитических обзоров . 5 (3): 2.

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