Министерство образования Республики Беларусь
Учреждение образования
"Гомельский государственный университет им. Ф. Скорины"
Математический факультет
Кафедра МПУ
Алгоритмы на графах. Поиск в глубину
Курсовая работа
Исполнитель:
Студентка группы М-43 Полякова А.Ю.
Научный руководитель:
Канд. физ-мат. наук, доцент Зверева Т.Е.
Гомель 2006
Содержание
Введение
1 Поиск в глубину
2 Задача "Дороги"
3 Задача "Перекрестки"
4 Задача "Скрудж Мак-Дак"
Заключение
Литература
Введение Прежде всего, несколько слов о том, как возникает понятие графа из естественных условий задач. Приведем несколько примеров.
Пусть мы имеем карту дорог, в которой для каждого города указано расстояние до всех соседних с ним. Здесь два города называются соседними, если существует дорога, соединяющая непосредственно эти два города.
Аналогично, можно рассмотреть улицы и перекрестки внутри одного города. Заметим, что могут быть улицы с односторонним движением.
Сеть компьютеров, соединенных проводными линиями связи.
Набор слов, каждое из которых начинается на определенную букву и заканчивается на эту же или другую букву.
Множество костей домино. Каждая кость имеет 2 числа: левую и правую половину кости.
Устройство, состоящее из микросхем, соединенных друг с другом наборами проводников.
Генеалогические деревья, указывающие родственные отношения между людьми.
И, наконец, собственно графы, указывающие отношения между какими либо абстрактными понятиями, например, числами.
Итак, неформально, граф можно определить как набор вершин (города, перекрестки, компьютеры, буквы, цифры кости домино, микросхемы, люди) и связей между ними: дороги между городами; улицы между перекрестками; проводные линии связи между компьютерами; слова, начинающиеся на одну букву и закачивающиеся на другую или эту же букву; проводники, соединяющие микросхемы; родственные отношения, например, Алексей - сын Петра. Двунаправленные связи, например, дороги с двусторонним движением, принято называть ребрами графа; а однонаправленные связи, например, дороги с односторонним движением, принято называть дугами графа. Граф, в котором вершины соединяются ребрами, принято называть неориентированным графом, а граф, в котором хотя бы некоторые вершины соединяются дугами, принято называть ориентированным графом.
1. Поиск в глубину Ниже приведен пример неориентированного графа с шестью вершинами.
При компьютерной обработке граф может задаваться списком ребер (дуг) для каждой вершины. Например, для графа, приведенного на примере, этот список выглядит так
Для хранения этой информации в памяти компьютера можно воспользоваться двумерным массивом G[1..N,1..M], где N - число вершин в графе, M - максимально возможное число ребер (дуг) у одной вершины графа. Для удобства обработки этой информации можно также иметь одномерный массив kG[1..N] - количества ребер (дуг) вершин графа.
Тогда для обработки списка связей текущей вершины U можно написать
for i:=1 to kG[U]
begin
V:=G[U,i];
end;
Тем самым, мы получаем обработку дуги, связывающей вершины U и V для всех вершин, непосредственно связанных с U.
Для обработки ВСЕХ связей всех вершин можно использовать поиск в глубину (DFS - Depth-First Search):
for U:=1 to N do Color[U]:=WHITE;
for U:=1 to N do
if color[U]=WHITE then DFS(U);
Procedure DFS(U:longint);
var
j : longint;
begin
color[U]:=GRAY;
for j:=1 to kG[U] do DFS(G[U,j]);
end;
Здесь
Color[U] = цвет вершины
WHITE (константа=1) - белый, если мы еще не посещали эту вершину
GRAY (константа=2) - серый, если мы посещали данную вершину
DFS(U) - рекурсивная процедура, которая вызывает себя для всех вершин, потомков данной вершины.
То есть, для обеспечения поиска в глубину на заданном графе G[1..N,1..M] с количествами дуг из вершин G[1..N], вначале мы устанавливаем всем вершинам цвет WHITE, а затем для всех вершин, которые еще не посещались (Color[G[U,j]]=WHITE) вызываем рекурсивную процедуру DFS.
Таким способом формируются все возможные маршруты в графе. ............
