Поиск в ширину на графах
Реферат
В данной работе: 7 рисунков, 1 программа, 1 приложение, 35 листов.
Ключевые слова: граф, алгоритм, поиск, ширина, программа, аргумент, элемент, массив, очередь, память, время, сравнение.
Цель работы: Исследовать эффективность алгоритма поиска в графе в ширину.
Результат работы программы: количество сравнений элемента с ключом поиска и время, за которое был найден элемент по данному алгоритму поиска.
Областью применение данного алгоритма может быть разнообразна, на пример при построении карт местности: вершины графа – города, связи – дороги.
Содержание
Введение…………………………………………………………………..5 стр.
Краткая теория………………………………………………………..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
столбцами,
соответствующими
ребрам.
Для ориентированного
графа столбец,
соответствующий
дуге
Лучшим способом представления графа является матрица смежности, определяемая как матрица В = [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
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 для произвольного
пустого графа
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