Как известно, представление графа в памяти преимущественно осуществляется двумя способами: матрицей смежности и списком смежности. Остановимся на первом из них.

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

Стоит отметить, что размер, выделяемый для хранения обыкновенной матрицы смежности, равняется где - количество вершин в графе.

Рассмотрим ориентированный граф, состоящий из четырех вершин:

Матрица смежности для такого графа будет иметь вид: (INF означает отсутствие ребра)

Битовая матрица смежности

Предположим, что нас не интересуют веса ребер графа, то есть будем говорить лишь о наличии ребра из одной вершины в другую. В таком случае размер, выделяемый под матрицу смежности ориентированного графа, можно уменьшить в 8 раз, соответственно до: . Назовем такую матрицу смежности битовой матрицей смежности для графа. Изначально она инициализирована нулями.

1. Рассмотрим функцию добавления значения в битовую матрицу смежности:

index = (line * numberOfVertices + column) / 8;
binaryMask = 128 >> ((line * numberOfVertices + column) % 8);
matrix[index] |= binaryMask;

Число 128 выбрано не просто так: его двоичное запись = 10000000₂. Здесь binaryMask представляет собой двоичную маску наличия ребра для текущей пары вершин line и column, формируемую побитовым сдвигом вправо. Дальнейшее выполнение "побитового или" позволяет добавить эту информацию в матрицу.

2. Рассмотрим функцию получения значения из битовой матрицы смежности:

index = (line * numberOfVertices + column) / 8;
binaryMask = 128 >> ((line * numberOfVertices + column) % 8);
binaryMask &= matrix[index];

Отличий от функции добавления значения в матрицу немного: вместо того, чтобы совершать операцию "побитого или" для матрицы, мы совершаем операцию "побитового и" для двоичной маски, которая даёт возможность узнать информацию о наличии ребра между вершинами line и column: если binaryMask == 0, то ребра нет, иначе - ребро есть.

Замечу, что в функциях, описанных выше, я полагал по определению, что line и column - это вершины графа, номера которых >= 1.

Пример работы с битовой матрицей смежности:

Пусть дан следующий ориентированный граф:

Размер, выделяемый для хранения битовой матрицы смежности будет равняться:

А значит такая матрица имеет вид: (индексация ячеек матрицы с нуля)

Добавим ребро 1-2:

₂

Добавим ребро 1-4:

₂

Добавим ребро 2-4:

₂

Наконец, добавим ребро 4-3:

₂

Теперь, используя полученную матрицу смежности, попробуем ответить на следующий вопрос: есть ли в этом графе ребро между вершинами 1-4?

10001000 & 10000000 = 1 => ребро есть.

А между вершинами 1-3?

00000010 & 00000001 = 0 => ребра нет.

Хранение половины (треугольной) матрицы смежности

В случае неориентированного графа мы получаем симметричную относительно главной диагонали матрицу:

Размер, выделяемый под треугольную матрицу смежности неориентированного графа, будет равняться: , если нам нужно хранить её главную диагональ.

Треугольная матрицы смежности такого графа примет вид:

1. Рассмотрим функцию получения индекса для этой матрицы:

maxVertex = max(line, column);
minVertex = min(line, column);
index = (maxVertex * (maxVertex - 1) / 2) + minVertex - 1;

2. Добавление и получение значений из треугольной матрицы смежности аналогично обычной матрице смежности, но по индексу, полученному выше.

Замечу, что здесь я так же предполагал line и column вершинами графа, номера которых >= 1.

Итоги

Эту статью я написал, потому что в своё время сам нуждался в данной информации. Благодарю всех читателей и надеюсь, что помог кому-нибудь.

Визуализацию графов проводил с помощью сайта: graphonline.ru.