Поиск в ширину на графах
Реферат
В данной работе: 7 рисунков, 1 программа, 1 приложение, 35 листов.
Ключевые слова: граф, алгоритм, поиск, ширина, программа, аргумент,
элемент, массив, очередь, память, время, сравнение.
Цель работы: Исследовать эффективность алгоритма поиска в графе в
ширину.
Результат работы программы: количество сравнений элемента с ключом
поиска и время, за которое был найден элемент по данному алгоритму поиска.
Областью применение данного алгоритма может быть разнообразна, на
пример при построении карт местности: вершины графа – города, связи –
дороги.
Содержание
Введение…………………………………………………………………..5 стр.
1. Краткая теория………………………………………………………..6 стр.
2. Анализ алгоритма……………………………………………………11 стр.
3. Спецификация задачи……………………………………………….14 стр.
3.1 Входные и выходные данные…………………………………14 стр.
3.2 Используемые процедуры…………………………………….14 стр.
4. Программа на языке Turbo Pascal..…………………………………15 стр.
4.1 Листинг программы…………..………….……………………15 стр.
4.2 Контрольный пример для тестирования №1….……………..26 стр.
4.3 Контрольный пример для тестирования №2….……………..26 стр.
4.4 Руководство пользователя…………………………………….27 стр.
5. Результаты тестирования……………………………………………28 стр.
Заключение………………………………………………………………33 стр.
Список используемой литературы……………………………………..34 стр.
Приложение А…………………………………………………………….35 стр.
Введение.
Графы встречаются в сотнях разных задач, и алгоритмы обработки графов
очень важны.
Существует множество разработанных алгоритмов для решения различных
задач из самых разных областей человеческой деятельности. Формулировка
задачи описывает, каким требованиям должно удовлетворять решение задачи, а
алгоритм, решающий эту задачу, находит объект, этим требованиям
удовлетворяющий. ([1])
В этой работе, мы не будем давать четкого определения алгоритма, а
попытаемся проанализировать и изучить алгоритм поиска в ширину в графе.
Поиском по заданному аргументу называется алгоритм, определяющий
соответствие ключа с заданным аргументом. Алгоритм поиска в ширину может
быть использован для просмотра созданного графа, чтобы узнать состав
информационных вершин для последующего поиска.
В результате работы алгоритма поиска заданная вершина может быть
найдена или может быть отмечено отсутствие ее в исходных данных.
Если заданная информационная вершина найдена, то происходит вывод об
успешном окончании поиска, вывод времени поиска и времени поиска ключа.
Краткая теория.
Очевидно, что наиболее понятный и полезный для человека способ
представления графа — изображение графа на плоскости в виде точек и
соединяющих их линий — будет совершенно бесполезным, если мы захотим решать
с помощью ЭВМ задачи, связанные с графами. Выбор соответствующей структуры
данных для представления графов имеет принципиальное влияние на
эффективность алгоритмов, поэтому мы подробнее остановимся на этой
проблеме. Мы покажем несколько различных способов представления и кратко
разберем их основные достоинства и недостатки.
Мы будем рассматривать как ориентированные, так и неориентированные
графы. Граф мы будем всегда обозначать G = (V,E), где V обозначает
множество вершин, а Е — множество ребер, причем Е ( V X V для
ориентированного графа и Е({{х,у}: х,у ( V ? х(у} для неориентированного
графа. Будем также использовать обозначения |V| = n и |Е| = m.
В теории графов классическим способом представления графа служит
матрица инциденций. Это матрица А с n строками, соответствующими вершинам,
и m столбцами, соответствующими ребрам. Для ориентированного графа столбец,
соответствующий дуге <x, y> ( E, содержит —1 в строке, соответствующей
вершине х, 1 в строке, соответствующей вершине у, и нули во всех остальных
строках (петлю, т. е. дугу вида <x, x>, удобно представлять иным значением
в строке х, например, 2). В случае неориентированного графа столбец,
соответствующий ребру {х,у}, содержит 1 в строках, соответствующих х и у, и
нули в остальных строках. Это проиллюстрировано на рис. 2.1. С
алгоритмической точки зрения матрица инциденций является, вероятно, самым
худшим способом представления графа, который только можно себе представить.
Во-первых, он требует nm ячеек памяти, причем большинство этих ячеек вообще
занято нулями. Неудобен также доступ к информации. Ответ на элементарные
вопросы типа «существует ли дуга <x,y>?», «к каким вершинам ведут ребра из
х?» требует в худшем случае перебора всех столбцов матрицы, а
следовательно, m шагов.
Лучшим способом представления графа является матрица смежности,
определяемая как матрица В = [b•j] размера nхm,
|<|<|<|<|<|<|<|
|1|1|3|3|5|5|6|
|,|,|,|,|,|,|,|
|2|3|2|4|4|6|5|
|>|>|>|>|>|>|>|
(а) 1 –1 –1
0 0 0 0 0
2 1
0 1 0 0 0 0
3 0
1 -1 -1 0 0 0
4 0
0 0 1 1 0 0
5 0
0 0 0 -1 -1 1
6 0
0 0 0 0 1 -1
|{|{|{|{|{|{|{|{|{|
|1|1|1|2|2|3|4|4|5|
|,|,|,|,|,|,|,|,|,|
|2|3|5|3|5|4|5|6|6|
|}|}|}|}|}|}|}|}|}|
(б) 1 1
1 1 0 0 0 0 0 0
2 1
0 0 1 1 0 0 0 0
3 0
1 0 1 0 1 0 0 0
4 0
0 0 0 0 1 1 1 0
5 0
0 1 0 1 0 1 0 1
6 0
0 0 0 0 0 0 1 1
Рис. 1. а) Ориентированный граф и его матрица инциденций;
б) Неориентированный граф и его матрица инциденций.
где bij = 1, если существует ребро, идущее из вершины х в вершину у, и bij
= 0 в противном случае. Здесь мы подразумеваем, что ребро {х, у}
неориентированного графа идет как от х к у, так и от у к х, так что матрица
смежности такого графа всегда является симметричной. Это проиллюстрировано
на рис. 2.
Основным преимуществом матрицы смежности является тот факт, что за один
шаг можно получить ответ на вопрос «существует ли ребро из х в y?».
Недостатком же является тот факт, что независимо от числа ребер объем
занятой памяти составляет n2. На практике это неудобство можно иногда
уменьшить, храня целую строку (столбец) матрицы в одном машинном слове —
это возможно для малых n.
В качестве еще одного аргумента против использования матрицы смежности
приведем теорему о числе шагов, которое
должен выполнить алгоритм, проверяющий на основе матрицы смежности
некоторое свойство графа.
Пусть Р — некоторое свойство графа P(G) = 0 или P(G)=1 в зависимости от
того, обладает или не обладает G нашим свойством. Предположим, что свойство
Р удовлетворяет следующим трем условиям:
(а) P(G)=P(G'), если графы G и G' изоморфны;
(б) P(G) = 0 для произвольного пустого графа <V,(> и P(G)=1 для
произвольного полного графа <V, P2(V)> с достаточно большим числом вершин;
1 2 3 4 5 6 1 2 3 4 5 6
1 0 1 1 0 0 0 1 0 1 1 0 1 0
2 0 0 0 0 0 0 2 1 0 1 0 1 0
3 0 1 0 1 0 0 3 1 1 0 1 0 0
4 0 0 0 0 0 0 4 0 0 1 0 1 1
5 0 0 0 1 0 1 5 1 1 0 1 0 1
6 0 0 0 0 1 0 6 0 0 0 1 1 0
Рис. 2. Матрицы инциденций для графов на рис.1.
(в) добавление ребра не нарушает свойства Р, т. е. P(G)<P(G') для
произвольных графов G=(F,E) и G'=(V, E'), таких что Е = Е'.
Примером такого свойства Р является существование цикла (в графе,
имеющем, по крайней мере три вершины).
Теорема . Если Р — свойство графа, отвечающее условиям (а), (б), (в), то
каждый алгоритм, проверяющий свойство Р (т. е. вычисляющий значение P(G)
для данного графа G) на основе матрицы смежности, выполняет в худшем случае
?(n2) шагов, где n — число вершин графа.
Эта теорема справедлива также для ориентированных графов и для свойств,
не зависящих от петель графа, т, е. отвечающих дополнительному условию
(г) P(G) = P(G') для произвольных ориентированных графов G = < V, E>, G’ =
< V, Е> U <v, v>>, v C V.
Более экономным в отношении памяти (особенно в случае, неплотных
графов, когда m гораздо меньше n2) является метод представления графа с
помощью списка пар, соответствующих его ребрам. Пара <x, у> соответствует
дуге <х, у>, если граф ориентированный, и ребру {х, y} в случае
неориентированного графа(рис. 3). Очевидно, что объем памяти в этом случае
составляет 2т. Неудобством является большое число шагов — порядка т в
худшем случае, — необходимое для получения множества вершин, к которым
ведут ребра из данной вершины.
Ситуацию можно значительно улучшить, упорядочив множество пар
лексикографически и применяя двоичный поиск, но лучшим решением во многих
случаях оказывается структура
|1|2 |
|1|3 |
|1|5 |
|2|3 |
|2|5 |
|3|4 |
|4|5 |
|4|6 |
|5|6 |
|1|2 |
|1|3 |
|3|2 |
|3|4 |
|5|4 |
|5|6 |
|6|5 |
Рис.3. Списки ребер соответствующие графам на рис.1.
данных, которую мы будем называть списками инцидентности. Она содержит для
каждой вершины v C V список вершин и, таких что v -> u (или v — ив случае
неориентированного графа). Точнее, каждый элемент такого списка является
записью г, содержащей вершину г. строка и указатель г. след на следующую
запись в списке (г. след = nil для последней записи в списке). Начало
каждого списка хранится в таблице НАЧАЛО; точнее, HAЧАЛО[v] является
указателем на начало списка, содержащего вершины из множества {u: v+u} ({u:
v - u} для неориентированного графа). Весь такой список обычно неформально
будем обозначать 3AПИСЬ[v], а цикл, выполняющий определенную операцию для
каждого элемента и из этого списка в произвольной, но четко установленной
последовательности, соответствующей очередности элементов в списке, будем
записывать «for u C ЗАПИСЬ [v] do ...».
Отметим, что для неориентированных графов каждое ребро {u, v}
представлено дважды: через вершину v в списке ЗАПИСЬ[u] и через вершину и в
списке ЗАПИСЬ[v]. Во многих алгоритмах структура графа динамически
модифицируется добавлением и удалением ребер. В таких случаях полагаем, что
в наших списках инцидентности элемент списка ЗАПИСЬ [u], содержащий вершину
и, снабжен указателем на элемент списка 3AПИCЬ[v], содержащий вершину и, и
что каждый элемент списка содержит указатель не только к следующему
элементу, но и к предыдущему. Тогда удаляя некоторый элемент
[pic]
Рис.4. Списки инцидентности ЗПИСЬ[v], v =V, соответствующие графам на
рис.1.
из списка, мы можем легко за число шагов, ограниченное константой, удалить
другой элемент, представляющий то же самое ребро, не просматривая список,
содержащий этот элемент.
Аналогичным способом определяем для каждой вершины и неориентированного
графа список ПРЕДШ[v], содержащий вершины из множества (u: u -> v).
Число ячеек памяти, необходимое для представления графа с помощью
списков инцидентности, будет, очевидно, иметь порядок m + n. На рис.4
представлены списки инцидентности, соответствующие графам на рис. 1.
2. Анализ алгоритма.
Рассмотрим метод поиска в графе, называемый поиском в ширину (англ:
breadth first search). Прежде чем описать его, отметим, что при поиске в
глубину чем позднее будет посещена вершина, тем раньше она будет
использована — точнее, так будет при допущении, что вторая вершина
посещается перед использованием первой. Это прямое следствие того факта,
что просмотренные, но еще не использованные вершины скапливаются в стеке.
Поиск в ширину, грубо говоря, основывается на замене стека очередью. После
такой модификации, чем раньше посещается вершина (помещается в очередь),
тем раньше она используется (удаляется из очереди). Использование вершины
происходит с помощью просмотра сразу всех еще не просмотренных соседей этой
вершины. Вся процедура поиска представлена ниже (данная процедура
используется также и для просмотра графа, и в псевдокоде, описанном ниже,
отсутствуют операторы, которые не используются для поиска).
1 procedure WS (v);
(*поиск в ширину в графе с началом в вершине v;
переменные НОВЫЙ, ЗАПИСЬ — глобальные *)
2 begin
3 ОЧЕРЕДЬ := ?; ОЧЕРЕДЬ <= v; НОВЫЙ [v] := ложь
4 while ОЧЕРЕДЬ ? ? do
5 begin р<= ОЧЕРЕДЬ; посетить р;
6 for u ? ЗАПИСЬ [р] do
7 if НОВЫЙ [u] then
8 begin ОЧЕРЕДЬ <= u; НОВЫЙ [u]:=ложь
9 end
10 end
11. end
Примечание: в 7-й строке псевдокода кроме условия НОВЫЙ[u] должно также
выполниться условие наличия связи (ребра) между v-й и u-й вершинами. Для
установки наличия ребра сначала в списке v-й вершины ищется информационное
значение и-й вершины. Если оно найдено, то ребро установлено, если нет, то
информационное значение v-й вершины ищется в списке и-й вершины, т.е.
наоборот. В результате добавления двух лишних циклов поиска общий алгоритм
поиска несколько теряет компактность, но на быстродействии в целом это не
сказывается.
1 procedure Write_S;
2 begin
3 for v ? V do НОВЫЙ[u]:= истина; (* инициализация *)
4 for v ? V do
5 if HOBЫЙ[v] then WG(v)
6 end
Способом, аналогичным тому, какой был применен для поиска в глубину,
можно легко показать, что вызов процедуры WS(v) приводит к посещению всех
вершин связной компоненты графа, содержащей вершину v, причем каждая
вершина просматривается в точности один раз. Вычислительная сложность
поиска в ширину также имеет порядок О(m + n), так как каждая вершина
помещается в очередь и удаляется из очереди в точности один раз, а число
итераций цикла 6, очевидно, будет иметь порядок числа ребер графа.
В очереди помещены сначала вершины, находящиеся на расстоянии 0 от v
(т. е. сама вершина v), затем поочередно все новые вершины, достижимые из
v, т. е. вершины, находящиеся на расстоянии 1 от v, и т. д. Под расстоянием
здесь мы понимаем длину кратчайшего пути. Предположим теперь, что мы уже
рассмотрели все вершины, находящиеся на расстоянии, не превосходящем r, от
v, что очередь содержит все вершины, находящиеся от v на расстоянии r, и
только эти вершины. Использовав каждую вершину р, находящуюся в очереди,
наша процедура просматривает некоторые новые вершины, и каждая такая новая
вершина u находится, очевидно, на расстоянии г + 1 от v. После