Как известно, представление графа в памяти преимущественно осуществляется двумя способами: матрицей смежности и списком смежности. Остановимся на первом из них.
Матрица смежности графа
Стоит отметить, что размер, выделяемый для хранения обыкновенной матрицы смежности, равняется 
где 
— количество вершин в графе.
Рассмотрим ориентированный граф, состоящий из четырех вершин:
Матрица смежности для такого графа будет иметь вид: (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: 
|
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: 
|
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: 
|
0 0 0 0 0 0 1 0 |
1 0 0 0 1 0 0 0 |
0 0 0 0 0 0 0 0 |
, если нам нужно хранить её главную диагональ.
Добавить комментарий