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

Матрица смежности имеет размерность n x n, где n - число вершин. Если элемент матрицы m_ij=1, то это говорит о том, что в графе имеется дуга, выходящая из i-ой вершины и входящая в j-ую вершину, т. е. за i-ой вершиной следует j-ая вершина.

Для этого графа матрица смежности имеет вид: Ris1-8-1.gif

Каждая строка матрицы может быть выражена как битовая строка, длиною в 32 бита, и хранится в одном машинном слове. Объем памяти, занимаемый матрицей, 11 слов. Если количество вершин в графе больше 32, то понадобится 2 слова на строку и объем памяти увеличится в 2 раза.

Номера вершин получены путем последовательной нумерации вершин. На самом деле номера вершин (номера операций или переходов) задаются другим способом. Например, нумерация операций обычно выполняется через 5. Поэтому необходима таблица адресов, в которой номеру вершины ставится в соответствие реальное обозначение номера операции или перехода ( 1 слово на обозначение операции (перехода)).

Таблица адресов.

Если структура выражена в виде матрицы смежности с битовыми строками, то ее суммарный объем памяти составит :

Если слово содержит 16 бит, то указанное выражение верно при n 16. Если 16 n 32, то на каждую строку требуется 2 слова. Суммарный объем памяти в этом случае составит

Если матрицу изобразить массивом размерности n x n и каждый элемент массива занимает 1 слово, то ее суммарный объем памяти составит: