Как известно, представление графа в памяти преимущественно осуществляется двумя способами: матрицей смежности и списком смежности. Остановимся на первом из них.
Матрица смежности графа
Стоит отметить, что размер, выделяемый для хранения обыкновенной матрицы смежности, равняется 
где 
- количество вершин в графе.
Рассмотрим ориентированный граф, состоящий из четырех вершин:
Матрица смежности для такого графа будет иметь вид: (INF означает отсутствие ребра)
| 7 |
| 5 |
|
|
| 9 |
|
|
|
|
|
| 2 |
|
Битовая матрица смежности
Предположим, что нас не интересуют веса ребер графа, то есть будем говорить лишь о наличии ребра из одной вершины в другую. В таком случае размер, выделяемый под матрицу смежности ориентированного графа, можно уменьшить в 8 раз, соответственно до: 
. Назовем такую матрицу смежности битовой матрицей смежности для графа. Изначально она инициализирована нулями.
Рассмотрим функцию добавления значения в битовую матрицу смежности:
index = (line * numberOfVertices + column) / 8;
binaryMask = 128 >> ((line * numberOfVertices + column) % 8);
matrix[index] |= binaryMask;Число 128 выбрано не просто так: его двоичное запись = 100000002. Здесь binaryMask представляет собой двоичную маску наличия ребра для текущей пары вершин line и column, формируемую побитовым сдвигом вправо. Дальнейшее выполнение "побитового или" позволяет добавить эту информацию в матрицу.
Рассмотрим функцию получения значения из битовой матрицы смежности:
index = (line * numberOfVertices + column) / 8;
binaryMask = 128 >> ((line * numberOfVertices + column) % 8);
binaryMask &= matrix[index];Отличий от функции добавления значения в матрицу немного: вместо того, чтобы совершать операцию "побитого или" для матрицы, мы совершаем операцию "побитового и" для двоичной маски, которая даёт возможность узнать информацию о наличии ребра между вершинами line и column: если binaryMask == 0, то ребра нет, иначе - ребро есть.
Замечу, что в функциях, описанных выше, я полагал по определению, что line и column - это вершины графа, номера которых >= 1.
Пример работы с битовой матрицей смежности:
Пусть дан следующий ориентированный граф:
Размер, выделяемый для хранения битовой матрицы смежности будет равняться: 
А значит такая матрица имеет вид: (индексация ячеек матрицы с нуля)
0 | 0 | 0 |
Добавим ребро 1-2: 
2
0 0 0 0 0 0 1 0 | 0 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0 |
Добавим ребро 1-4: 
2
0 0 0 0 0 0 1 0 | 1 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0 |
Добавим ребро 2-4: 
2
0 0 0 0 0 0 1 0 | 1 0 0 0 1 0 0 0 | 0 0 0 0 0 0 0 0 |
Наконец, добавим ребро 4-3: 
2
0 0 0 0 0 0 1 0 | 1 0 0 0 1 0 0 0 | 0 0 0 1 0 0 0 0 |
Тепе��ь, используя полученную матрицу смежности, попробуем ответить на следующий вопрос: есть ли в этом графе ребро между вершинами 1-4?
10001000 & 10000000 = 1 => ребро есть.
А между вершинами 1-3?
00000010 & 00000001 = 0 => ребра нет.
Хранение половины (треугольной) матрицы смежности
В случае неориентированного графа мы получаем симметричную относительно главной диагонали матрицу:
| 4 | 8 |
4 |
| 17 |
8 | 17 |
|
Размер, выделяемый под треугольную матрицу смежности неориентированного графа, будет равняться: 
, если нам нужно хранить её главную диагональ.
Треугольная матрицы смежности такого графа примет вид:
| 4 |
| 8 | 17 |
|
Рассмотрим функцию получения индекса для этой матрицы:
maxVertex = max(line, column);
minVertex = min(line, column);
index = (maxVertex * (maxVertex - 1) / 2) + minVertex - 1;Добавление и получение значений из треугольной матрицы смежности аналогично обычной матрице смежности, но по индексу, полученному выше.
Замечу, что здесь я так же предполагал line и column вершинами графа, номера которых >= 1.
Итоги
Эту статью я написал, потому что в своё время сам нуждался в данной информации. Благодарю всех читателей и надеюсь, что помог кому-нибудь.
Визуализацию графов проводил с помощью сайта: graphonline.ru.
