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

Реферат
В данной работе: 7 рисунков, 1 программа, 1 приложение, 35 листов.

Ключевые слова: граф, алгоритм, поиск, ширина, программа, аргумент, элемент, массив, очередь, память, время, сравнение.

Цель работы: Исследовать эффективность алгоритма поиска в графе в ширину.

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

Областью применение данного алгоритма может быть разнообразна, на пример при построении карт местности: вершины графа – города, связи – дороги.

Краткая теория………………………………………………………..6 стр.

Анализ алгоритма……………………………………………………11 стр.

Спецификация задачи……………………………………………….14 стр.

3.1 Входные и выходные данные…………………………………14 стр.

3.2 Используемые процедуры…………………………………….14 стр.

Программа на языке Turbo Pascal..…………………………………15 стр.

4.1 Листинг программы…………..………….……………………15 стр.

4.2 Контрольный пример для тестирования №1….……………..26 стр.

4.3 Контрольный пример для тестирования №2….……………..26 стр.

4.4 Руководство пользователя…………………………………….27 стр.

Результаты тестирования……………………………………………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,2>

<1,3>

<3,2>

<3,4>

<5,4>

<5,6>

<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,2}

{1,3}

{1,5}

{2,3}

{2,5}

{3,4}

{4,5}

{4,6}

{5,6}

( б) 1 1 1 1 0 0 0 0 0 0