2.3. ГРАФЫ

Сейчас мы введем математическое понятие графа и те структуры данных, которые обычно применяются для его представления.

Определение. Граф состоит из конечного непустого множества узлов V и множества ребер Если ребра представлены в виде упорядоченных пар узлов, то граф называется ориентированным; называется началом, концом ребра Если ребра — неупорядоченные пары (множества) различных вершин, также обозначаемые то граф называют неориентированным 2).

Если в ориентированном графе пара принадлежит множеству ребер то узел называется смежным с узлом Говорят, что ребро идет Число узлов, смежных с узлом называется полустепенью его исхода.

Если ребро неориентированного графа то мы считаем, что так что то же самое ребро. Узел называется смежным с узлом если (а значит, и принадлежит Степень узла — это число узлов, смежных с ним.

Путем в ориентированном или неориентированном графе называют последовательность ребер вида Говорят, что этот путь идет из и имеет длину Часто такой путь представляют последовательностью узлов, лежащих на нем. В вырожденном случае один узел обозначает путь длины 0, идущий из этого узла в него же. Путь называется простым, если все ребра и все узлы на нем, кроме, быть может, первого и последнего, различны. Цикл — это простой путь длины не менее 1, который начинается и кончается в одном и том же узле. Заметим, что в неориентированном графе длина цикла должна быть не менее 3.

Известно несколько представлений графа Один из них — матрица смежностей, т.е. матрица А размера состоящая из и 1, в которой тогда и только тогда, когда есть ребро из узла в узел Представление в виде матрицы

смежностей удобно для тех алгоритмов на графах, которым часто нужно знать, есть ли в графе данное ребро, ибо время, необходимое для определения наличия ребра, фиксировано и не зависит от Основной недостаток применения матрицы смежностей заключается в том, что она занимает память объема даже тогда, когда граф содержит только ребер. Уже начальное заполнение матрицы смежностей посредством "естественной" процедуры требует времени что сводит на нет алгоритмы сложности при работе с графами, содержащими лишь ребер. Хотя разработаны методы для преодоления этой трудности (см. упр. 2.12), почти неизбежно возникают другие проблемы, которые приводят к тому, что алгоритмы сложности основанные на работе с матрицей смежностей, встречаются редко.

Интересной альтернативой является представление строк и (или) столбцов матрицы смежностей в виде двоичных векторов. Такое

Рис. 2.6. Ориентированный граф и его представления: а — ориентированный граф; б - матрица смежностей; в — списки смежностей; г - табличное представление списков смежностей.

представление может способствовать значительной эффективности алгоритмов на графах.

Еще одно возможное представление графа — с помощью списков. Списком смежностей для узла называется список всех узлов смежных с Граф можно представить с помощью списков смежностей, по одному для каждого узла.

Пример 2.2. На рис. 2.6,а изображен ориентированный граф, содержащий четыре узла, а на рис. его матрица смежностей. На рис. 2.6,в показаны четыре списка смежностей, по одному для каждого узла. Например, из узла 1 в узлы 2 и 4 идут ребра, так что список смежностей для 1 содержит компоненты 2 и 4, связанные в смысле рис. 2.1.

Табличное представление списков смежностей приведено на рис. 2.6,г. Каждая из первых четырех ячеек в массиве СЛЕДУЮЩИЙ содержит указатель на первый узел списка смежностей, а именно указывает на первый узел списка смежностей для узла Заметим, что поскольку в списке смежностей для узла 3 нет узлов. Остальные составляющие массива СЛЕДУЮЩИЙ представляют ребра графа. Массив содержит узлы из списков смежностей. Таким образом, список смежностей узла 1 начинается в ячейке 5, ибо это показывает, что есть ребро Равенства означают, что есть ребро а что больше нет ребер, начинающихся в

Заметим, что представление графа в виде списков смежностей требует памяти порядка Представлением с помощью списков смежностей часто пользуются, когда

Если граф неориентирован, то каждое ребро представляется дважды: один раз в списке смежностей для и один раз в списке смежностей для В этом случае можно добавить новый массив, называемый СВЯЗЬ, чтобы коррелировать оба экземпляра неориентированного ребра. Таким образом, если ячейка, соответствующая узлу в списке смежностей для то ячейка, соответствующая узлу в списке смежностей для

Если мы хотим с удобством удалять ребра из неориентированного графа, то списки смежностей можно связать дважды (как описано в разд. 2.1). Это обычно бывает нужно потому, что даже если удалять всегда ребро ( стоящее первым в списке смежностей узла все равно может оказаться, что ребро, идущее в обратном направлении, стоит в середине списка смежностей узла Чтобы быстро удалить ребро из списка смежностей для надо уметь быстро находить ячейку, содержащую предыдущее ребро в этом списке смежностей.