Машинное представление графов
Самый приятный и полезный для человека способ представить граф – изобразить его на плоскости в виде точек и соединяющих их линий. Очевидно, что для ЭВМ он совершенно бесполезен… Поскольку выбор для этой цели определенной структуры данных очень сильно влияет на эффективность алгоритма, рассмотрим несколько способов машинного представления графов.
Матрицы смежности– самый худший с алгоритмической точки зрения способ. Это матрицы nm в строках перечисляются вершины, в столбцах – ребра (см. таблицу и рис. 8.3).
Матрица смежности
| 1-2 | 1-3 | 1-4 | 2-3 | 3-4 | |
Рис. 8.3. Модельный граф
Этот способ требует nm ячеек памяти, причем большинство из ячеек заняты нулями. Ответ на элементарный вопрос: «к каким вершинам ведут ребра из x?», требует перебора всех столбцов, т.е. m шагов.
Матрица инциденцийимеет размер n´n. Если существует ребро (x–y), то в клетках с координатами (x, y) и (y, x) ставится 1.
Матрица инциденций графа G (рис. 8.3):
Независимо от числа ребер требуется объем памяти n´n, но за один шаг можно ответить на вопрос: «существует ли ребро из x в y?».
Также граф можно представить в виде списка пар, соответствующих ребрам:
Список ребер графа G (рис. 8.3)
Объем памяти равен 2m, но попробуйте ответить на вопрос: «к каким вершинам ведут ребра из вершины x?».
Наиболее удобным машинным представлением графа являются списки инцидентности.
Каждой вершине v 
V ставим в соответствие список вершин, соединенных ребрами с вершиной v. Для неориентированного графа каждое ребро (v–u) будет представлено дважды: в списке для v и в списке для u. Начало каждого списка будет храниться в одномерном массиве НАЧАЛО длины n. По вершине v находим НАЧАЛО[v] – в этой ячейке хранится указатель на начало списка вершин, соединенных с v. Каждый элемент такого списка – запись, состоящая из двух полей:
| Вершина | Указатель на следующую запись | UZL | NEXT |
Если вершина 1 соединена с 2 и 3, то ее список выглядит как на рис. 8.4.
Рис. 8.4. Список инцидентности
Весь список для вершины v будем называть ЗАПИСЬ[v]. Цикл, перебирающий все элементы этого списка, будем записывать «for u ЗАПИСЬ[v]».
Число ячеек памяти, необходимое для представления графа списками инцидентности, имеет порядок O(n+m).
Создадим ЗАПИСЬ[1] для списков инцидентности (рис. 8.5) графа G (рис. 8.3).
Рис. 8.5. Список инцидентности к графу с рис. 8.3
Указатели на начало каждой цепи объединены в массив НАЧАЛО и инициализируются перед созданием цепи (рис. 8.6).
Рис. 8.6. Первый шаг создания списков
Записи для ребер, выходящих из узла (1), создаются динамически. Рассмотрим подробно этот механизм (рис. 8.7).
|
Рис. 8.7. Шаги 2-5 создания списков
Очевидно, что запись, подключенная первой, оказывается в конце цепи, а последняя – в начале. Таким образом, дисциплина обслуживания соответствует стеку. Вообще, набор стандартных подпрограмм для работы с динамическими списками включает в себя процедуру вталкивания в стек push, функцию выталкивания из стека pop и функцию выталкивания из очереди poptail. Опишем их во фрагменте 1.
ФРАГМЕНТ 1
| Procedure Push(Var p: PT; k: integer); {p – указатель на начало стека; k – вталкиваемый элемент} var p1: PT; begin {push} new(p1); {новая пустая запись} p1^.uzl:= k; {заполнение ее данными} p1^.next:= p; {помещение ее перед верхушкой стека} p:= p1 {указатель начала указывает на новую запись} end; {push} |
| Function Pop(Var p: PT): integer; {для непустого стека} {p – указатель на начало стека} var p1: PT; begin {pop} pop:= p^.uzl; {вытолкнем верхушку стека} p1:= p; {укажем p1 на обреченную запись} p:= p^.next; {верхушка стека – следующая запись} dispose(p1) {освобождение памяти} end; {pop} |
| Function Poptail(Var p: PT): integer; {для непустой очереди} {p – указатель на начало очереди} begin {poptail} if p^.next = NIL then {в очереди ровно один элемент} poptail:=pop(p) else {будем сдвигать указатель вправо, пока не найдем последний элемент списка} poptail:=poptail(p^.next) {рекурсия} end; {poptail} |
Ясно, что формирование всех цепей списков инцидентности нужно делать в цикле. Сделаем это во фрагменте 2.
ФРАГМЕНТ 2