Введение

1. Краткая теория

2. Анализ алгоритма

3. Спецификация задачи

3.1 Входные и выходные данные

3.2 Используемые процедуры

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

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

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

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

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

5. Результаты тестирования

Заключение

Список используемой литературы

Приложение А

Введение.

Графы встречаются в сотнях разных задач, и алгоритмы обработки гра­фов очень важны.

Существует множество разработанных алгоритмов для решения различных задач из самых разных областей человеческой деятельности. Формулировка задачи описывает, каким требованиям должно удовлетворять решение задачи, а алгоритм, решающий эту задачу, находит объект, этим требованиям удовлетворяющий. ([1])

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

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

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

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

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 –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 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.