"Чистая"
и прикладная математика

Структуры данных для представления графа в памяти ЭВМ

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

Матрицы инцидентности

Списки инцидентности

Преимущества и недостатки каждого способа

Зададимся вопросом: можно ли поместить слона в компьютер? Ответ: можно, если слона смоделировать в виде графа, в котором вершинами являются части его тела, а рёбра соединяют те части тела, которые соединены в слоне как биологическом объекте. При этом получившийся граф должен быть представлен в памяти компьютера в понятном компьютеру виде.

В связи с широким применением графов в программировании и информационных технологиях вообще возникает вопрос о представлении графа в виде структуры данных. Различные способы представления графов в памяти компьютера отличаются объёмом занимаемой памяти и скоростью выполнения операций над графами.

Наиболее часто используются три такие структуры данных - матрица смежности, матрица инцидентности и список инцидентности.

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

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

Матрица смежности S - это квадратная и обычно булева матрица. Квадратная, потому что и число строк, и число столбцов равно n - числу вершин графа. Булева, потому что в ячейку матрицы записывается единица, если вершины u и v соединены ребром, и нуль, если данные вершины не соединены.

Таким образом, элемент матрицы определяется из следующего выражения:

Пример 1. Составить матрицу смежности для графа, представленного на рисунке ниже.

Ответ.

V12345
101100
210011
310001
401000
501100

Таким образом, матрица смежности симметрична относительно главной диагонали.

В случае взвешенного графа в соответствующую ячейку матрицы смежности вписывается число w, если существует ребро между вершинами u и v с весом w.

Матрицы инцидентнсти

Матрица инцидентности H - это булева матрица размера n x m, где n - число вершин графа, m - число рёбер графа. Обычно в матрице инцидентности строки соответствуют вершинам графа, а столбцы - рёбрам графа.

Таким образом, элемент матрицы определяется из следующего выражения:

Пример 2. Составить матрицу инцидентности для графа, представленного на рисунке ниже.

Ответ.

V1-21-32-42-53-5
111000
210110
301001
400100
500011

На сайте есть пример реализации на языке программирования С++ алгоритма обхода в глубину графа, представленного матрицей инцидентности.

Списки инцидентности

Графы значительного объёма целесообразно хранить в памяти компьютера в форме списков инцидентности.

Список инцидентности одной вершины графа включает номера вершин, смежных с ней.

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

Пример 3. Составить списки инцидентности для графа, представленного на рисунке ниже.

Ответ.

1:2→3
2:1→4→5
3:1→5
4:2
5:2→3

Преимущества и недостатки каждого способа

Матрицы смежности и инцидентности целесообразнее использовать когда:

  • число вершин графа невелико;
  • число рёбер графа относительно большое;
  • в алгоритме часто требуется проверять, соединены ли между собой две вершины;
  • в алгоритме используются фундаментальные понятия теории графов, например, связность графа.

Из-за последнего обстоятельства матрицы чаще используются в теоретических исследованиях графов.

Списки инцидентности целесообразнее использовать когда:

  • число вершин графа велико;
  • число рёбер графа относительно невелико;
  • граф формируется по какой-либо модели;
  • во время действия алгоритма часто требуется модифицировать граф;
  • в алгоритме часто используются локальные свойства вершин, например, например, окрестности вершин.

На практике списки чаще используются в прикладных целях.

Весь блок "Теория графов"