Представление и обработка данных в виде графов
Графы формально описывают множество близких ситуаций. Самым привычным примером служит карта автодорог, на которой изображены перекрестки и связывающие их дороги. Перекрестки являются вершинами графа, а дороги — его ребрами. Графы могут быть ориентированы (подобно улицам с односторонним движением) или взвешены, когда каждой дороге приписана стоимость путешествия по ней (если, например, дороги платные).
С формальной точки зрения граф представляет собой упорядоченную пару множеств G = ( V, Е), первое из которых состоит из вершин (узлов) графа, а второе — из его ребер. Ребро связывает между собой две вершины. При работе с графами часто решается вопрос, как проложить путь из ребер от одной вершины графа к другой. В этом случае говорят о движении по ребру, что означает переход из вершины А графа в другую вершину 5, связанную с ней ребром АВ (ребро графа, связывающее две вершины, для краткости обозначается этой парой вершин). В этом случае говорят, что ребро А примыкает к ребру В или что эти две вершины соседние.
Граф может быть ориентированным или нет. Ребра неориентированного графа, чаще всего называемого просто графом, можно проходить в обоих направлениях (рис. 14.26). В этом случае ребро — это неупорядоченная пара вершин, его концов.
5
Граф G = ({1, 2, 3, 4, 5 }, {{1, 2}, {1, 3 }, Рис. 14.26. Неориентированный граф
В ориентированном графе, или орграфе, ребра представляют собой упорядоченные пары вершин: первая вершина — это начало ребра, вторая — его конец (рис. 14.27).
Полный граф — это граф, в котором каждая вершина соединена со всеми остальными. Количество ребер в полном графе без петель с N вершинами равно (Л/2 -ЛГ)/2. В полном ориентированном графе разрешается переход из любой вершины в любую другую. Поскольку в графе переход по ребру разрешается в обоих направ-
14.4. Представление и обработка данных разного типа 421
лениях, а переход по ребру в орграфе — только в одном, в полном орграфе в два раза больше ребер, то есть их количество равно N2 - N.
4 *—'
Ориентированный
Рис. 14.27.Ориентированный граф
Подграф (VS,ES) графа или орграфа (VyE) состоит из некоторого подмножества вершин, Vs С V, и некоторого подмножества ребер, их соединяющих, Es С Е.
Путь в графе или орграфе — это последовательность ребер, по которым можно поочередно проходить. Другими словами, путь из вершины А в вершину В начинается в Л и проходит по набору ребер до тех пор, пока не будет достигнута вершина В. С формальной точки зрения путь из вершины Vx в вершину Vy — это последовательность ребер графа:
Необходимо, чтобы любая вершина встречалась на таком пути не более, чем однажды. У всякого пути есть длина — количество ребер в нем. Длина пути АВ, ВС, СДДЕ равна 4.
Граф или орграф называется связным, если всякую пару узлов можно соединить по крайней мере одним путем. Цикл — это путь, который начинается и кончается в одной и той же вершине. В ациклическом графе или орграфе циклы отсутствуют. Связный ациклический граф называется неукорененным деревом. Структура неуко-рененного дерева такая же, как и у дерева, только в нем не выделен корень. Однако каждая вершина неукорененного дерева может служить его корнем.
Информацию о графах или орграфах в пригодном для обработки компьютерными алгоритмами виде можно хранить двумя способами: в виде матрицы примыканий и в виде списка примыканий^.
Матрица примыканий обеспечивает быстрый доступ к информации о ребрах графа, однако, если в графе мало ребер, эта матрица будет содержать гораздо больше пустых клеток, чем заполненных. Длина списка примыканий пропорциональна числу ребер в графе, однако при пользовании списком время получения информации о ребре увеличивается.
1 В определенных конкретных случаях может потребоваться представления и в других формах, также пригодных к обработке на компьютере: в виде матриц инцидентности или матриц смежности, а также других структур для представления «веса» и «цвета» связей, пометок вершин и т. д.