Определение 16

Структуры данных для представления графов

Информацию о графах и орграфах можно хранить двумя способами:

1) в виде матрицы примыканий;

2) в виде списка примыканий.

Матрица примыканий обеспечивает быстрый доступ к информации о ребрах графа. Однако, если в графе мало ребер, то эта матрица будет содержать гораздо больше пустых клеток, чем заполненных.

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

Таким образом, ни один из этих методов не превосходит другой заведомо.

Матрица примыканий графа с числом вершин записывается в виде двумерного массива размера .

В каждой ячейке этого массива записано число «нуль» за исключением лишь тех случаев, когда из вершины в вершину ведет ребро. Тогда в ячейке записывается «единица».

Более строго это можно записать так:

.

Рассмотрим, как будут выглядеть матрицы примыканий в конкретных примерах.