Машинное представление графов

Самый приятный и полезный для человека способ представить граф — изобразить его на плоскости в виде точек и соединяющих их линий. Очевидно, что для ЭВМ он совершенно бесполезен… Поскольку выбор для этой цели определенной структуры данных очень сильно влияет на эффективность алгоритма, рассмотрим несколько способов машинного представления графов.

МАТРИЦЫ СМЕЖНОСТИ — самый худший с алгоритмической точки зрения способ. Это матрицы nm: в строках перечисляются вершины, в столбцах ребра.

МАТРИЦА СМЕЖНОСТИ

	1-2	1-3	1-4	2-3	3-4

Рисунок 8.3

Этот способ требует nm ячеек памяти, причем большинство из ячеек заняты нулями. Ответ на элементарный вопрос: «к каким вершинам ведут ребра из x?», требует перебора всех столбцов, т.е. m шагов.

МАТРИЦА ИНЦИДЕНЦИЙ имеет размер nn. Если существует ребро x—y, то в клетках с координатами (x, y) и (y, x) ставится 1.

МАТРИЦА ИНЦИДЕНЦИЙ графа G (рисунок 8.3)

Независимо от числа ребер требуется объем памяти n, но за один шаг можно ответить на вопрос: «существует ли ребро из x в y?».

Граф можно представить в виде списка пар, соответствующих ребрам:

СПИСОК РЕБЕР графа G (рисунок 8.3)

Объем памяти равен 2*m, но попробуйте ответить на вопрос: «к каким вершинам ведут ребра из вершины 4?».

Лучшее решение — структура, которую называют СПИСКИ ИНЦИДЕНТНОСТИ.

Каждой вершине v V ставим в соответствие список вершин, соединенных ребрами с вершиной v. Для неориентированного графа каждое ребро (v—u) будет представлено дважды: в списке для v и в списке для u. Начало каждого списка будет храниться в одномерном массиве НАЧАЛО длины n. По вершине v находим НАЧАЛО[v] — в этой ячейке хранится указатель на начало списка вершин, соединенных с v. Каждый элемент такого списка — запись, состоящая из двух полей:

Вершина

указатель на следующую запись

 

UZL

NEXT

Если вершина 1 соединена с 2 и 3, то ее список выглядит так:

Рисунок 8.4

Весь список для вершины v будем называть ЗАПИСЬ[v]. Цикл, перебирающий все элементы этого списка, будем записывать «for u ЗАПИСЬ[v]»

Рисунок 8.5

Число ячеек памяти, необходимое для представления графа списками инцидентности, имеет порядок O(n+m).

Опишем списки инцидентности на языке ПАСКАЛЬ во фрагменте 1:

ФРАГМЕНТ 1

CONST N=4; M=5; TYPE PT=^ZT; ZT= record Uzl: integer; Next: PT end; VAR START: array [1..N] of PT; u,v,uzel: integer; reb, e: integer; p, p1: PT;

for reb:=1 to M do begin write (' Начало и конец', reb, 'ребра'); read(u,v); {push — процедура вталкивания в стек} push(START[u], v); push(START[v], u); end; {Списки формируются по принципу стека, т.к. порядок элементов внутри списка не важен.}

Создадим ЗАПИСЬ[1] для списков инцидентности (рисунок 8.5).

Указатели на начало каждой цепи объединены в массив НАЧАЛО и инициализируются перед созданием цепи.

Рисунок 8.6

Записи для ребер, выходящих из узла (1), создаются ДИНАМИЧЕСКИ. Рассмотрим подробно этот механизм.

Рисунок 8.7

Рисунок 8.8

Очевидно, что запись, подключенная первой, оказывается в конце цепи, а последняя окажется в начале. Таким образом, дисциплина обслуживания соответствует стеку.

?Вопрос 1. Опишите механизм выталкивания из стека, т.е.удаления из начала цепи последней подключенной записи.

Ясно, что формирование всех цепей списков инцидентности нужно делать в цикле. Сделаем это во фрагменте 2.

Ответы.

Ответ 1. Набор стандартных подпрограмм для работы с динамическими списками включает в себя процедуру вталкивания в стек push, функцию выталкивания из стека pop и функцию выталкивания из очереди poptail.

ФРАГМЕНТ 2

Procedure Push(Var p: PT); {p — указатель на начало стека} var p1: PT; begin new(p1); {новая пустая запись} p1^.uzl:=k; {заполнение ее данными} p1^.next:=p; {помещение ее перед верхушкой стека} p:=p1 {указатель начала указывает на новую запись} end;

Function Pop(Var p: PT):integer; {для непустого стека} {p — указатель на начало стека} var p1: PT; begin pop:=p^.uzl; {вытолкнем верхушку стека} p1:=p; {укажем p1 обреченную запись} p:=p^.next; {верхушка стека — следующая запись} dispose(p1) {освобождение памяти} end;

Function Poptail(Var p: PT):integer; {для непустой очереди} {p — указатель на начало очереди} begin if p^.next=nil then {очередь состоит ровно из одного элемента} poptail:=pop(p) else {будем сдвигать указатель вправо, пока не найдем последний элемент списка} poptail:=poptail(p^.next) {рекурсия} end;

 

Поиск в глубину в графе

Существует много различных алгоритмов, в основе которых лежит систематический перебор вершин графа, при котором каждая вершина просматривается ровно один раз. Будем рассматривать такие методы обхода или поиска в графе, что:

а) алгоритм решения легко «погружается» в этот метод;

б) каждое ребро графа анализируется число раз, ограниченное константой.

Опишем классический метод поиска в неориентированном графе — метод ПОИСКА В ГЛУБИНУ (англ. depth first search).

Общая идея следующая.Начинаем поиск с некоторой фиксированной вершины k (корня). Затем выбираем одну из смежных (соединенных ребрами) с ней вершин. Назовем эту вершину u. Далее процесс поиска повторяется от u.

Пусть на каком-то этапе мы находимся в вершине v. Если среди ее соседей есть хотя бы одна НОВАЯ (еще непросмотренная) вершина w, то просматриваем ее. После этого w перестает быть новой, и дальнейший поиск продолжаем с w.

Если же у вершины v НЕТ ни одной НОВОЙ «соседки», то говорим, что v ИСПОЛЬЗОВАНА, и возвращаемся на ШАГ НАЗАД — в вершину, из которой попали в v. Просмотренные, но еще не использованные вершины накапливаются в стеке. Использованные вершины удаляются из стека. Когда стек опустеет, то у связного графа будут просмотрены все вершины, у несвязного — компонента связности, содержащая вершину k.

Рисунок 8.10

?Вопрос 1. Когда следует прервать работу алгоритма, если мы ищем путь от 1 до 5? Где находится путь?

Поиск в глубину можно записать с помощью рекурсивной процедуры GL.

Переменная НОВЫЙ — глобальная.

1 procedure GL(v) {поиск в глубину из вершины v}

2 begin рассмотреть v; НОВЫЙ[v]:=ложь;

3 for u ЗАПИСЬ[v] do {перебор всех соседей v}

4 if НОВЫЙ[u] then GL[u]

5 end {v использована}

Поиск в глубину в произвольном (необязательно связном) графе проводится согласно следующему алгоритму:

1 begin

2 for v V do НОВЫЙ[v]:=истина; {инициализация}

3 for v V do {перебор всех вершин графа}

4 if НОВЫЙ[v] then GL(v)

5 end {поиск окончен, все вершины просмотрены}

Покажем теперь, что этот алгоритм просматривает каждую вершину в точности ОДИН РАЗ и СЛОЖНОСТЬ его порядка O(n+m).

Первый вызов GL (v) для некоторой вершины v влечет за собой просмотр всех вершин компоненты связности графа, содержащей v. Это обеспечивает цикл 3 процедуры GL: после просмотра v будет вызвана GL для всех ее новых соседей.

Каждая вершина просматривается ровно один раз — просматриваются только новые вершины, сразу после просмотра НОВЫЙ[v]:=ложь.

Будут просмотрены все вершины — цикл 3 основного алгоритма.

Оценим теперь вычислительную сложность алгоритма.

Циклы 2 и 3 основного алгоритма содержат n шагов, не считая вызовы процедуры GL. Строка 2 процедуры GL для ВСЕХ вызовов повлечет O(n) шагов. Полное число шагов цикла 3 процедуры GL для ВСЕХ рекурсивных вызовов будет порядка m — числа всех ребер, т.к. от вершины к ее соседям мы двигаемся по ребрам.

Суммарная сложность алгоритма О(n+m).

В связи с важностью поиска в глубину для проектирования алгоритмов на графах представим также НЕРЕКУРСИВНУЮ версию процедуры GL.

Рекурсия устраняется стандартным способом: каждая просмотренная вершина помещается в СТЕК и удаляется из стека после использования.

1 procedure GL1(v); {поиск в глубину,начиная с v}

2 begin

3 СТЕК:=NIL; СТЕК<=v;

4 рассмотреть v;

5 НОВЫЙ[v]:=ложь; {v помещается в СТЕК}

6 while СТЕК do

7 begin

8 verh:=top(СТЕК); {читаем верхний элемент СТЕКА}

{будем искать первую новую «соседку» элемента verh}

9 if НАЧАЛО [verh]=hil then b:=ложь

10 else b:=not НОВЫЙ [НАЧАЛО[verh]^.uzl];

{НАЧАЛО[verh]^.uzl-номер первой вершины в списке
ЗАПИСЬ[verh]}

11 while b do

12 begin

13 НАЧАЛО[verh]:=НАЧАЛО[verh]^.next;

{переводим указатель НАЧАЛО на следующую запись в

списке ЗАПИСЬ[verh]}

14 if НАЧАЛО [verh]=nil then b:=ложь

15 else b:=not НОВЫЙ[НАЧАЛО[verh]^.uzl]

{проверяем, будет ли вершина следующей записи новой}

16 end;

17 if НАЧАЛО[verh]=nil then {найдена новая
вершина!}

18 begin

19 verh:=НАЧАЛО[verh]^.uzl;

20 СТЕК<=verh; {новая вершина помещена в СТЕК}

21 рассмотреть verh; НОВЫЙ[verh]:=ложь

22 end

23 else {вершина verh использована}

24 verh<=СТЕК {удалить verh из СТЕКа}

25 end {while СТЕК <> NIL}

26 end; {procedure GL1}

Корректность процедуры GL1 доказывается аналогично GL.

Ответы.

Ответ 1. Когда 5 попадет в стек. В стеке.

Поиск в ширину в графе

При ПОИСКЕ В ГЛУБИНУ просмотренные, но еще не использованные вершины скапливались в стеке. Чем позднее была просмотрена вершина, тем раньше ее удаляли из стека. Заменим стек ОЧЕРЕДЬЮ.

Механизм подключения элемента к началу очереди полностью совпадает с вталкиванием в стек (процедура push). Механизм ВЫТАЛКИВАНИИЯ ИЗ ОЧЕРЕДИ (функции poptail) — первым из очереди удаляется первый попавший туда элемент.

Основная идея ПОИСКА В ШИРИНУ — у вершины v просматриваются и помещаются в очередь СРАЗУ ВСЕ ее новые «соседи», после чего v становится использованной и удаляется из очереди.

Рисунок 8.12

Поиск в ширину можно использовать для нахождения КРАТЧАЙШЕГО пути между парой фиксированных вершин s и t. Так как мы находим сразу всех соседей, поиск, как волна от источника, равномерно распространяется во все стороны. Поэтому в очереди сначала находятся все вершины, удаленные от s на расстояние 1, через некоторое время — все вершины, удаленные на расстояние 2 и т.д. Понятно, что путь, найденный таким образом, будет кратчайшим.

Рисунок 8.13

Процедура поиска в ширину SH:

1 procedure SH(v);

{поиск в ширину с началом в вершине v}

2 begin

3 ОЧЕРЕДЬ:=NIL; ОЧЕРЕДЬ<= v; НОВЫЙ[v]:=ложь;

{v помещается в очередь}

4 while ОЧЕРЕДЬ<>NIL do

5 begin

6 niz <=ОЧЕРЕДЬ;

{выталкивание из очереди нижнего элемента}

7 for u ЗАПИСЬ[niz] do

{ищем ВСЕХ новых соседей узла niz}

8 if НОВЫЙ[u] then

9 begin

10 ОЧЕРЕДЬ <= u; НОВЫЙ[u]:=ложь

11 end

12 end {while ОЧЕРЕДЬ <>NIL}

13 end;

Как и для поиска в глубину, легко показать, что каждая вершина просматривается ровно один раз и вычислительная сложность равна O(n+m).

Чтобы найти кратчайший путь, нужно немного модифицировать процедуру SH. Во-первых, добавить одномерный массив ПРЕД по числу вершин графа. Пусть во время работы процедуры в вершину u₂ мы попали из u₁: u₁ была предыдущей для u₂, поэтому ПРЕД[u₂]:=u₁. Во-вторых, чтобы массив ПРЕД заполнялся именно так, изменим строку 10 процедуры SH:

9 begin

10 ОЧЕРЕДЬ<=u; НОВЫЙ[u]:=ложь;

ПРЕД[u]:=niz; {добавка}

Итак, чтобы найти кратчайший путь из s в t, вызовем модифицированную SH (s).

Как только конец пути t попадет в очередь, поиск следует прекратить. Каким образом извлечь путь от s до t из массива ПРЕД?

Рассмотрим последовательность вершин, где u₁=ПРЕД[u₂]. В t мы попали из u, в u из v и т.д., пока не встретим s. Эта последовательность — путь из s в t. Первоначальная инициализация массива ПРЕД: ПРЕД[u]:=u.

?Вопрос 1. Как будет заполнен массив ПРЕД при поиске в ширину на рисунок 12 в момент помещения в очередь вершины 5?

Метод поиска в ширину применим для определения связных компонент графа. Вызвав SH (s), просмотрим все вершины u, для которых существует путь из s в u.

Ответы.

Ответ 1. ПРЕД[1]=1; ПРЕД[2]=ПРЕД[3]=1; ПРЕД[4]=3; ПРЕД[5]=2.