Матрица смежности имеет размерность n x n, где n - число вершин. Если элемент матрицы mij=1, то это говорит о том, что в графе имеется дуга, выходящая из i-ой вершины и входящая в j-ую вершину, т. е. за i-ой вершиной следует j-ая вершина.
Каждая строка матрицы может быть выражена как битовая строка, длиною в 32 бита, и хранится в одном машинном слове. Объем памяти, занимаемый матрицей, 11 слов. Если количество вершин в графе больше 32, то понадобится 2 слова на строку и объем памяти увеличится в 2 раза.
Номера вершин получены путем последовательной нумерации вершин. На самом деле номера вершин (номера операций или переходов) задаются другим способом. Например, нумерация операций обычно выполняется через 5. Поэтому необходима таблица адресов, в которой номеру вершины ставится в соответствие реальное обозначение номера операции или перехода ( 1 слово на обозначение операции (перехода)).
|
|
|
|
|
|
|
|
|
|
|
|
Если структура выражена в виде матрицы смежности с битовыми строками, то ее суммарный объем памяти составит :
|
|
Если слово содержит 16 бит, то указанное выражение верно при n 
16. Если 16
n 32, то на каждую строку требуется 2 слова. Суммарный объем памяти в
этом случае составит
|
|
Если матрицу изобразить массивом размерности n x n и каждый элемент массива занимает 1 слово, то ее суммарный объем памяти составит:
|
|