Исследование эффективности алгоритма поиска в графе в ширину. Матрицы инциденций для графов. Анализ алгоритма поиска в графе. Основные входные и выходные данные, процедуры, их обозначение в листинге программы. Текст программы на языке TURBO PASCAL.
Аннотация к работе
Очевидно, что наиболее понятный и полезный для человека способ представления графа - изображение графа на плоскости в виде точек и соединяющих их линий - будет совершенно бесполезным, если мы захотим решать с помощью ЭВМ задачи, связанные с графами. Будем рассматривать как ориентированные, так и неориентированные графы. Граф будем всегда обозначать G = (V,E), где V обозначает множество вершин, а Е - множество ребер, причем Е I V X V для ориентированного графа и EI{{х,у}: х,у I V ? х?у} для неориентированного графа.Рассмотрим метод поиска в графе, называемый поиском в ширину (англ.: breadth first search). Прежде чем описать его, отметим, что при поиске в глубину, чем позднее будет посещена вершина, тем раньше она будет использована - точнее, так будет при допущении, что вторая вершина посещается перед использованием первой. После такой модификации, чем раньше посещается вершина (помещается в очередь), тем раньше она используется (удаляется из очереди). 3 ОЧЕРЕДЬ := ?; ОЧЕРЕДЬ <= v; НОВЫЙ [v] := ложь.ver - массив вершин графа, заполняемый случайным образом целыми числами в диапазоне от 0 до 1000;.Make_Graph - процедура создания графа в динамической памяти; WS - процедура просмотра графа с v-той вершины методом поиска в ширину; Write_S - процедура инициализации признаков просмотра вершин и управляющая процедурой WS; Sort - процедура сортировки вершин графа по неубыванию. 4. Текст программы на языке TURBO PASCALlist= record inf: word;. end;. ver: array[1..maxraz] of word; {массив вершин}. ocher: array[1..maxraz 1] of integer;. key,kols,t,tm: longint;.55 497-§661 497-§ КОЛ-ВО РЕБЕР СОЗДАННОГО ГРАФА: 4 Содержание информационных вершин: 74 174 55 497 661 Примечание: символ «§» соответствует концу списка (nil). Полученный граф изображен на рисунке 6 Рисунок 6 - Результат теста 4.3 Контрольный пример для тестирования №2 Количество вершин графа - 7, ребра между ними формируются случайным образом. Список инцидентности созданного графа: 704 66-373-434-§ 434 373-§ 766 706-373-434-§ 373 66-§706 66-704-§ 454 706-66-373-§ КОЛ-ВО РЕБЕР СОЗДАННОГО ГРАФА: 13 Содержание информационных вершин: 704 434 766 373 66 706 454 Примечание: символ «§» соответствует концу списка (nil). Полученный граф изображен на рисунке 7 Рисунок 7- Результат теста 2.При запуске программы на экране появляется основное меню программы, которое состоит из четырех пунктов: 1. Создание графа.Исследуем результаты работы программы, для чего сначала измерим время поиска для трех графов из 100, 200 и 400 элементов, отсортированных в порядке возрастания и не отсортированных и сравним полученные результаты. Количество информационных вершин - 10, вершины не отсортированы, их содержание: 97 920 635 286 590 938 981 716 427 474. Вершина графа 427 найдена!. Количество сравнений: 9.0.