Лабораторная работа №6

Графы как структура данных

1. Цель работы

Цель данной работы – изучить:

1. различные способы представления графа в памяти компьютера;
2. методы поиска в графе (поиск в глубину и поиск в ширину);
3. переборные алгоритмы, основанные на методах поиска в графе.

2. Краткие сведения из теории

2.1. Основные понятия и определения

Термин граф вводится в дискретной математике. С частным случаем графов – деревьями – мы уже познакомились. Теперь настала очередь графов.

Граф G определяется двумя множествами – множеством вершин V и множеством пар вершин E. Пишут G=(V, E). Если пара вершин неупорядочена, то ее принято называть ребром. Если упорядочена – дугой. Граф, состоящий только из ребер называется неориентированным графом. Граф, содержащий только дуги, - ориентированным графом или орграфом.

В реальных задачах граф может отражать объекты и связи между ними. При этом двусторонние связи будут отображаться в ребра графа, а однонаправленные связи – в дуги. Примером может служить сеть автомобильных дорог города. В данном случае вершинами графа будут перекрестки, ребрами – улицы с двусторонним движением, дугами – улицы с односторонним движением.

На рисунке граф можно представить точками, соответствующими вершинам графа, линиями, соединяющими вершины и соответствующими ребрам графа, и направленными от вершины к вершине линиями, соответствующими дугам графа.

Две вершины x и y, соединенные ребром (x, y), называют смежными вершинами. Если вершины соединены дугой (x, y), то вершина x смежна вершине y, а обратной смежности нет.

Два ребра называют смежными ребрами, если они имеют общую вершину.

Ребро и любая из двух его вершин называются инцидентными.

Любому ребру или вершине может быть присвоен вес. Вес вершины – число, которое характеризует вершину, вес ребра – число, характеризующее отношение между двумя вершинами. Например, для графа автомобильных дорог вес ребра может означать длину дороги от одного перекрестка до другого.

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

2.2. Способы представления графа в памяти

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

При дальнейшем изложении будем предполагать, что вершины графа пронумерованы от 1 до N, а ребра – от 1 до M. Каждому ребру и каждой вершине сопоставлен вес – целое положительное число.

Для каждого способа хранения будем определять пространственную сложность и временную сложность следующих операций:

• проверка смежности вершин x и y;
• перечисление всех вершин смежных с x;
• определение веса ребра (x, y);
• определение веса вершины x;
• перечисление всех ребер (x, y);
• перечисление ребер, инцидентных вершине x;
• перечисление вершин, инцидентных ребру s.

2.2.1. Матрица смежности

Матрица смежности это двумерный массив размером N*N:

Type
  TAdjacencyMatrix = array [1..N, 1..N] of Integer;
Var
  Graph: TAdjacencyMatrix;

При этом

Пространственная сложность этого способа O(N²). Временные сложности сведены в таблицу

Этот способ очень хорош, когда нам надо часто проверять смежность или находить вес ребра по двум заданным вершинам.

2.2.2. Матрица инцидентности

Матрица инцидентности это двумерный массив размером N*M:

Type
  TIncidenceMatrix = array [1..N, 1..M] of Integer;
Var
  Graph: TIncidenceMatrix;

При этом

Пространственная сложность этого способа O(N*M). Временные сложности сведены в таблицу

Матрица инцидентности лучше всего подходит для операции «перечисление ребер, инцидентных вершине x».

2.2.3. Списки смежных

Списки смежных это одномерный массив размером N, содержащий список вершин смежных с данной:

Type
  TAdjacencyList = array [1..N] of record
    Count: Integer; {число элементов в списке}
    List: array[1..N] of record {список}
      Node, {номер смежной вершины}
      Weight: Integer; {вес ребра}
    end;;
  end;
Var
  Graph: TAdjacencyList;

Пространственная сложность этого способа O(N²). Временные сложности сведены в таблицу

Хранение списков в динамической памяти позволяет сократить объем расходуемой памяти, так как в этом случае не будет резервироваться место под N соседей для каждой вершины.

Этот способ хранения лучше всех других подходит для операции «перечисление всех вершин смежных с x»

2.2.4. Перечень ребер

Списки смежных это одномерный массив размером N, содержащий список вершин смежных с данной:

Type
  TBranchList = array [1..M] of record
    Node1, Node2, {пара вершин, которые связывает ведро}
    Weight: Integer; {вес ребра}
  end;
Var
  Graph: TBranchList;

Пространственная сложность этого способа O(M). Временные сложности сведены в таблицу

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

2.3. Методы поиска в графе

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

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

2.3.1. Поиск в глубину

Поиск в глубину стремится проникнуть подальше от исходной вершины. Идея этого метода следующая. На каждом шаге метода:

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

Для программы понадобится булевский массив:

Visited: array[1..N] of Boolean;

В этом массиве будем помечать уже посещенные вершины. Первоначально массив должен быть заполнен значениями false (ни одна из вершин не была посещена). Также договоримся хранить граф в виде списков смежности.

Теперь реализуем рекурсивную логику алгоритма в рекурсивной программе (v – номер вершины):

procedure DepthSearch(v: Integer);
Var
  j: Integer;
begin
  Visited[v] := True;
  Write(‘Вершина ’, v, ‘посещена.’);
  for j := 1 to Graph[v].Count do
    if not Visited[Graph[v].List[j].Node] then
      DepthSearch(Graph[v].List[j].Node);
end;

procedure DepthSearch2(v: Integer);
Var
  Way: array[1..N] of record {содержимое стека возврата}
    Node, {номер вершины}
    Number: Integer; {число рассмотренных элементов 
                      списка смежности}
  end;
  Count: Integer; {размер (вершина) стека возврата}
  Current, j: Integer;
  Found: Boolean;
begin
  Count := 1; Way[Count].Node := v; Way[Count].Number := 0;
  Visited[v] := True;
  Write(‘Вершина ’, v, ‘посещена.’);
  repeat
    Current := Way[Count].Node; 
    Found := False;
    for j := Way[Count].Number+1 to Graph[Current].Count do
    begin
      if not Visited[Graph[Current].List[j]] then
      begin
        Inc(Count);
        Way[Count].Node := Graph[Current].List[j];
        Way[Count].Number := 0;
        Visited[Graph[Current].List[j]] := True;
        Write(‘Вершина ’, Graph[Current].List[j],
          ‘посещена.’);
        Found := True;
        Break;
      end;
    end;
    if not Found then
    Dec(Count);
  until Count = 0;
end;

2.3.2. Поиск в ширину

Этот алгоритм поиска в графе также называют волновым алгоритмом из-за того, что обход графа идет по принципу распространения волны. Волна растекается равномерно во все стороны с одинаковой скоростью. На i-ом шаге будут выписаны все вершины, достижимые за i ходов, если ходом считать переход из одной вершины в другую.

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

procedure WidthSearch(v: Integer);
Var
  Delayed: array[1..N] of Integer; {очередь}
  Count, {хвост очереди}
  Head: Integer; {голова очереди}
  Current, j: Integer;
begin
  Count := 1; Head := 0; Delayed[Count] := v;
  Visited[v] := True;
  Write(‘Вершина ’, v, ‘посещена.’);
  repeat
    Inc(Head); Current := Delayed[Head];
    for j := 1 to Graph[Current].Count do
      if not Visited[Graph[Current].List[j]] then
      begin
        Inc(Count); 
        Delayed[Count] := Graph[Current].List[j];
        Visited[Graph[Current].List[j]] := True;
        Write(‘Вершина ’, Graph[Current].List[j],
          ‘посещена.’);
      end;
  until Count = Head;
end;

2.4. Методы поиска и переборные алгоритмы

Переборные алгоритмы по сути своей тоже являются алгоритмами поиска, как правило, поиска оптимального (или возможного, или всех возможных) решения(-ий). При этом решение строится не сразу – оно конструируется постепенно. В этом случае можно вести речь о переборе вершин дерева вариантов. Вершины такого графа будут промежуточными или конечными вариантами, а ребра будут указывать пути конструирования вариантов.

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

Лабиринт, состоящий из проходимых и непроходимых клеток, задан матрицей A размером M*N. Элемент матрицы A[i, j]=0, если клетка (i, j) проходима. В противном случае A[i, j]=1.

Требуется найти кратчайший путь из клетки (1, 1) в клетку (M, N).

Фактически дана матрица смежности (только в ней нули заменены единицами, а единицы – нулями). Лабиринт представляет собой граф.

Вершинами дерева вариантов в данной задаче являются пути, начинающиеся в клетке (1, 1). Ребра – показывают ход конструирования этих путей и соединяют два пути длины k и k+1, где второй путь получается из первого добавлением к пути еще одного хода.

2.4.1. Перебор с возвратом

Этот метод, по-английски называемый backtracking (некоторые авторы и по-русски пишут «бектрекинг»), основан на методе поиска в глубину. С житейской точки зрения перебор с возвратом – это метод проб и ошибок («попробуем сходить в эту сторону: не получится – вернемся и попробуем в другую»). Поскольку речь идет о переборе дерева вариантов методом поиска в глубину, то во время работы алгоритма надо хранить текущий путь в дереве. Этот путь представляет собой стек Way.

Вернемся к нашей задаче. Пусть мы находимся в некоторой клетке (в начале работы алгоритма – в начальной клетке (1, 1)). Далее

if <есть клетка-сосед Neighbor отсутствующая в Way,
  в которую на этом пути еще не ходили> then
begin
  <добавить Neighbor в Way>;
  текущая клетка := Neighbor;
end else
  <извлечь из Way>;

Из приведенного выше фрагмента программы ясно, почему этот метод называется перебором с возвратом. Возврату здесь соответствует операция <извлечь из Way>, которая уменьшает длину Way на 1.

Перебор заканчивается, когда Way пуст и делается попытка возврата назад. В этой ситуации возвращаться уже некуда.

Way – это путь текущий, но в процессе работы нам надо хранить еще и оптимальный путь OptimalWay.

Finish := False;
<сделать пустым Way>;
<добавить в Way (1, 1)>
<сделать OptimalWay бесконечно длинным>;
repeat
  if <есть клетка-сосед Neighbor отсутствующая в Way,
    в которую на этом пути еще не ходили> then
  begin
    <добавить Neighbor в Way>;
    текущая клетка := Neighbor;
    if (<текущая клетка – (M, N)>)and
     (<длина OptimalWay больше длины Way>) then
      OptimalWay := Way;
  end else
  begin
    if <Way пуст> then
      Finish := True
    else
      <извлечь из Way>;
  end;
until Finish;

Заметим, что алгоритм можно усовершенствовать, если не позволять, чтобы длина Way была больше или равна длине OptimalWay. В этом случае если и будет найден какой-то вариант, он заведомо не будет оптимальным. Такое усовершенствование в общем случае означает, что как только текущий путь станет заведомо неоптимальным, надо вернуться назад. В некоторых случаях это улучшение алгоритма позволяет сильно сократить перебор.

Посмотрим работу алгоритма с указанным усовершенствованием на примере лабиринта, изображенного на рисунке (строки нумеруются снизу вверх, столбцы – слева направо). Фиксируем порядок посещения соседних клеток: левая, верхняя, правая, нижняя. В таблице будем фиксировать лишь содержимое Way и OptimalWay в моменты переходов от движения вперед к возврату назад и наоборот от возвратов назад к движению вперед.

В рассмотренном примере оптимальным оказался путь длиной 8 ходов, проходящий через клетки (1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 4), (4, 4), (5, 4), (5, 5).

Этот переборный алгоритм основан на поиске в ширину и состоит из двух этапов:

1. Распространение волны.
2. Обратный ход.

Распространение волны и есть собственно поиск в ширину. При обратном ходе, начиная с конечной вершины идет восстановление пути, по которому мы в нее попали. Важно, что восстановление начинается с конца (с начала оно зачастую невозможно).

Рассмотрим метод на примере из раздела 2.4.1.

Распространение волны отображено на рисунке и в таблице. Цифра на рисунке означает шаг метода (номер фронта волны), на котором клетка посещается.

При обратном ходе задаемся вопросом: откуда мы попали в текущую клетку. Чтобы ответить на этот вопрос здесь надо запомнить ответ при распространении волны. Клетку, из которой пришли в текущую, присоединяем к началу пути. Таким образом продолжаем восстановление, пока не вернемся в начальную точку.

В данном примере при обратном ходе мы получим путь, проходящий через клетки (1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 4), (4, 4), (5, 4), (5, 5). Этот результат совпадает с полученным перебором с возвратом.

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

1. Что такое граф? Что такое ребро и дуга графа?
2. Что такое ориентированный граф и неориентированный граф?
3. Какие вершины называют смежными? Какие ребра называют смежными? Что означает слово инцидентные?
4. Что такое вес вершины, вес ребра? Привести примеры из реальных задач.
5. Обосновать, как получаются временные сложности в разделе 2.1.1.
6. Обосновать, как получаются временные сложности в разделе 2.1.2.
7. Обосновать, как получаются временные сложности в разделе 2.1.3.
8. Обосновать, как получаются временные сложности в разделе 2.1.4.
9. Что хранит нерекурсивная программа из раздела 2.3.1. в стеке возврата? (имеется в виду как содержимое стека в целом, так и содержимое отдельных элементов).
10. Каковы сложности в среднем и лучшем случае алгоритма поиска в глубину?
11. В чем разница между алгоритмами поиска в ширину и поиска в глубину?
12. Согласны ли Вы с хранением графа в виде списков смежности в алгоритмах поиска? Почему?
13. Чему будет равен OptimalWay по окончании работы программы из раздела 2.4.1., если оптимальный путь не существует?
14. Назовите два основных этапа волнового алгоритма. Что происходит на каждом из этапов?

Перед выполнением индивидуального задания ознакомиться с методами поиска в графе и построенными на их основе переборными алгоритмами.

При выполнении индивидуального задания придерживаться следующей последовательности действий:

1. изучить словесную постановку задачи;
2. выбрать переборный алгоритм;
3. разработать программу, решающую поставленную задачу;
4. оттестировать и отладить программу;
5. написать и представить к защите отчет по работе.

1. Титульный лист.
2. Словесная постановка задачи.
3. Алгоритм решения задачи в текстуальном виде.
4. Обоснование правильности выбора алгоритма.
5. Листинг программы.
6. Ответы на контрольные вопросы по согласованию с преподавателем.

Задание 1. Напишите программу закраски замкнутого контура.

Указание. Можно воспользоваться любым алгоритмом обхода вершин графа. Вершинами графа в данном случае будут пикселы изображения, ребрами графа – отношение соседства точек.

Задание 2. Из клетчатого поля размером M*N клеток вырезали некоторые клетки. Определить, на сколько частей распадется поле.

Указание. Воспользоваться алгоритмом закраски замкнутого контура (смотрите предыдущую задачу): находим незакрашенную клетку и начинаем закраску от нее – число таких закрасок будет равно числу частей, на которые распадается поле.

Задание 3. Даны обозначения двух полей шахматной доски. Найти минимальное число ходов, которые нужны шахматному коню для перехода с первого поля на второе.

Указание. Воспользоваться волновым алгоритмом. Вершинами графа будут позиции на шахматной доске, а ребрами – ходы коня.

Задание 4. На шахматной доске расположен белый король и N черных пешек. Король может брать пешки и ходить по обычным шахматным правилам (то есть не вставая на битое поле). Однако пешки, в отличие от обычной шахматной игры, не могут перемещаться по доске. Разработайте алгоритм, определяющий может ли король с поля A1 попасть на поле H8.

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

Задание 5. Имеется механизм, состоящий из N расположенных «в одной плоскости» и свободно надетых на зафиксированные оси пронумерованных шестеренок, зубья которых соприкасаются друг с другом. Информация о механизме ограничивается тем, что для каждой из шестеренок перечислены все те, с которыми данная находится в непосредственном зацеплении. Создайте алгоритм, определяющий, есть ли такая шестеренка, поворачивая которую, мы приведем в движение весь механизм.

Указание. Механизм можно привести в движение только, если шестеренки не блокируют друг друга (не пытаются крутить друг друга в разные стороны). Проверить это можно модификацией волнового алгоритма.

Задание 6. На случай экстренной ситуации на предприятии имеется список сотрудников и список оповещения вида:

(фамилия оповещающего, фамилия оповещаемого)

Один оповещающий может оповестить за день 3 человек.

Напишите программу, определяющую:

а) полон ли список оповещения, то есть будут ли оповещены все сотрудники;

б) сколько людей будет оповещено за K дней.

Указание. Это типичная задача на применение волнового алгоритма.

Задание 7. Имеется N элементов a, b, c, … и множество F, содержащее некоторый набор упорядоченных пар этих элементов (так называемое бинарное отношение). Напишите алгоритм построения транзитивного замыкания F, то есть множества, содержащего F и удовлетворяющего следующему свойству: если в нем есть пары (a, b) и (b, c), то в нем есть и пара (a, c).

Указание. Воспользуйтесь волновым алгоритмом.

Задание 8. Пусть граф является моделью печатной платы, то есть вершины графа – посадочные места для элементов микросхем, а ребра – возможные соединения. Пусть задан массив пар Item номеров вершин, которые надо попарно соединить (построить путь из Item[K, 1] до Item[K,2] при всех K) непересекающимися путями (пути состоят из различных вершин и ребер). Напишите алгоритм решающий эту задачу.

Указание. Воспользуйтесь перебором с возвратом.

Задание 9. Напишите алгоритм составления кроссвордов из заданного набора слов на заданной кроссвордной сетке.

Указание. Воспользуйтесь перебором с возвратом.

Задание 10. Напишите алгоритм, находящий строку длиной 100 символов, состоящую только из букв «A», «B», «C», такую, что в ней никакие две соседние подстроки не равны друг другу.

Указание. Воспользуйтесь перебором с возвратом.

Задание 11. Написать программу, расставляющую N ферзей на шахматной доске размером N*N так, что ни один не находится под боем.

Указание. Воспользуйтесь перебором с возвратом.