График (абстрактный тип данных)
-
Основы графов в информатике
- Граф — это абстрактный тип данных для реализации теории графов в математике.
- Структура графа состоит из вершин и ребер, которые могут быть связаны с атрибутами.
-
Операции с графами
- Основные операции включают проверку наличия ребер, перечисление соседей, добавление и удаление вершин и ребер.
- Существуют операции для получения и установки значений, связанных с вершинами и ребрами.
-
Структуры данных для графического представления
- Матричные представления эффективны для плотных графов, а списки смежности — для разреженных.
- Улучшение операций в списках смежности возможно с использованием хэш-таблиц или бинарных деревьев поиска.
-
Параллельные представления графов
- Параллельные представления графов важны для решения проблем с низкой локальностью и высоким соотношением доступа к данным и вычислений.
- В моделях с общей памятью эффективны списки смежности, в распределенной памяти — разбиение графа на разделы.
-
Сжатые представления графов
- Сжатые представления разработаны для уменьшения требований к вводу-выводу и памяти в областях, где используются графики с триллионами ребер.
-
Обход графа
- Поиск в ширину и поиск в глубину — это подходы для изучения всех узлов в компоненте графа.
-
Дополнительные ресурсы
- Ссылки на Boost Graph Library, Networkx, GraphMatcher и GraphBLAS для графических операций.
Полный текст статьи: