Практическая работа №7 по дисциплине: Теория алгоритмов наименование работы: Поиск в графе.


Смоленский колледж телекоммуникаций
(филиал) федерального государственного образовательного
бюджетного учреждения высшего профессионального образования
«Санкт-Петербургский государственный университет телекоммуникаций
им. проф. М.А. Бонч-Бруевича»
Практическая работа №7
по дисциплине: Теория алгоритмов
наименование работы: Поиск в графе.
для специальностей: 230115, 09.02.03
работа рассчитана на 2 часа
составлена преподавателем: Скряго О.С.
Смоленск, 2014
1. Цель работы: овладеть навыками составления алгоритмов поиска в графе.
2. Литература:
2.1. Балюкевич, Э.Л. Математическая логика и теория алгоритмов [Электронный ресурс]: учебное пособие/ Балюкевич Э.Л., Ковалева Л.Ф.— Электрон. текстовые данные.— М.: Евразийский открытый институт, 2009.— 188 c. ISBN:978-5-374-00220-1
2.2. Верещагин, Н.К. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции [Электронный ресурс]/ Верещагин Н.К., Шень А.— Электрон. текстовые данные.— М.: МЦНМО, 2012.— 160 c. ISBN:978-5-4439-0014-8
2.3. Гаврилов, Г.П. Задачи и упражнения по дискретной математике [Электронный ресурс]: учебное пособие/ Гаврилов Г.П., Сапоженко А.А.— Электрон. текстовые данные.— М.: ФИЗМАТЛИТ, 2009.— 416 c. ISBN:978-5-9221-0477-7
3. Подготовка к работе:
3.1. Повторить тему «Алгоритмы на графах».
3.2. Подготовить бланк отчета (см.п.7).
3.3. Ответить на вопросы допуска:
3.3.1. Сформулировать определение графа?
3.3.2. Какие ребра называются смежными?
3.3.3. Какой граф называется взвешенным?
4. Основное оборудование: ПЭВМ
5. Задание:
Выполните задание согласно варианту.
5.1. Составить алгоритмы и разработать программы поиска в глубину и поиска в ширину. Граф задан матрицей смежности.
Вариант 1 Вариант 2 Вариант 3
1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6
1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 1 1 2 1 1 2 1 1 1 3 1 1 1 1 1 3 1 1 3 1 1
4 1 1 1 4 1 4 1 5 1 1 5 1 5 1
6 1 1 1 1 1 6 6
Вариант 4 Вариант 5 Вариант 6
1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6
1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 2 1 1 2 1 1 1 1 3 1 1 3 1 1 1 3 1 1 1 1
4 1 4 1 1 4 1 1 1
5 1 5 1 5 1 1 1 1 1
6 6 6 1 1 1 Вариант 7 Вариант 8 Вариант 9
1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6
1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 2 1 2 1 1 1 1
3 1 1 1 3 1 1 1 3 1 1 4 1 4 1 1 4 1 1 1
5 1 5 1 5 1 1 1
6 6 6 1 1 1 Вариант 10 Вариант 11 Вариант 12
1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6
1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 1 2 1 1 2 1 1 3 1 1 3 1 1 3 1 1 1 1 1
4 1 4 1 1 4 1 1 1 1
5 1 5 5 1 1 1
6 6 6 1 1 1 1 Вариант 13 Вариант 14 Вариант 15
1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6
1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 1 1 2 1 1 1 2 1 1 1 1 3 1 1 3 1 1 1 3 1 1 1 1
4 1 4 1 1 4 1 1 1 1 5 1 5 1 5 1 1 1 1 6 6 6 1 1 6. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ.
6.1. Ознакомиться с заданием.
6.2. Определить номер варианта (в соответствии с номером в журнале).
6.3. Выполнить задание 5 письменно.
6.4. Сообщить преподавателю о выполненных заданиях.
6.5. Повторить правила техники безопасности:
Правила техники безопасности в компьютерном классе.
Перед началом работы необходимо убедиться в отсутствии видимых повреждений аппаратуры.
Работа с компьютером производится строго по указаниям преподавателя.
Запрещается:
Разъединять или соединять разъемы аппаратуры;
Прикасаться к экрану монитора;
Включать и выключать аппаратуру без указания преподавателя;
Класть какие-либо предметы на монитор, системный блок или клавиатуру;
Работать во влажной одежде, а также влажными или грязными руками;
Пытаться самостоятельно исправлять возникшую в аппаратуре неисправность.
Включите компьютер.
Включите в сеть стабилизатор напряжения (если он имеется).
Включите принтер (если он имеется).
Включите монитор.
Включите системный блок (большая кнопка на передней панели).
Выключение компьютера.
Завершите выполнение всех программ.
Выполните команду: Пуск Завершение работы Выключить компьютер (Alt+F4→ Завершение работы).
Выключите системный блок.
6.6. Приступить к выполнению тестирование программ.
6.7.Оформить отчет.
7. Содержание отчета:
7.1. Название и цель работы.
7.2 Ответы на вопросы допуска.
7.2. Указать номер варианта, привести условия задач своего варианта.
7.3. Представить выполненные задания согласно варианта, текст программы с комментариями.
7.4. Ответы на контрольные вопросы.
8. Контрольные вопросы:
8.1. Где в жизни можно наблюдать использование графов?
8.2. Какие способы описания графа вы знаете?
8.3. Объясните суть алгоритма поиска в глубину?
8.4. Объясните суть алгоритма поиска в ширину?
8.5. Как граф представляется в памяти компьютера?

Составил преподаватель __________________________Скряго О.С.
9. Приложение:
Граф — совокупность точек, соединённых между собой линиями. Точки называют вершинами графа. Они могут изображаться точками, кружочками, прямоугольниками и пр. Линии, соединяющие вершины, называются дугами (если задано направление от одной вершины к другой) или рёбрами (если направленность двусторонняя, то есть направления равноправны).
Две вершины, соединенные ребром (дугой) называются смежными.
Вершины и рёбра графа могут характеризоваться некоторыми числовыми величинами. Например, может быть известна длина ребра или «стоимость прохождения» по нему. Такие характеристики называют весом, а граф называется взвешенным.
Граф однозначно задан, если заданы множество его вершин, множество рёбер (дуг) и указано, какие вершины с какими рёбрами (дугами) соединены и, возможно, указаны веса вершин и рёбер (дуг). Определение всех этих элементов и составляет суть формализации в этом случае.
Представление графа в памяти компьютера
Определим граф G как пару (V,E), где V – конечное множество вершин, а Е – множество неупорядоченных и упорядоченных пар вершин. Мощности множеств V и E обозначим буквами N и M. (Мощность конечного множества совпадает с количеством элементов в нем.) Неупорядоченная пара вершин называется ребром, а упорядоченная пара – дугой. Граф, содержащий только ребра, называется неориентированным; граф, содержащий только дуги – ориентированным или орграфом. Единственное структурное различие между ориентированным и неориентированным графом состоит в том, что в первом случае граничные вершины ребра образуют упорядоченную пару, а во втором неупорядоченную. Говорят, что ребро (U, V) соединяет вершины U и V. Вершины, соединенные ребром, называются смежными. Ребра, имеющие общую вершину, также называются смежными. Ребро и любая из его 2-х вершин называютя инцидентными. Каждый граф можно представить на плоскости множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам и дугам. Направление дуги графа на рисунке обозначается стрелкой. В 3-х мерном пространстве любой граф можно представить таким образом, что линии не будут пересекаться.
В прикладных задачах теории графов необходимость введения ориентации ребер возникает по 2-м причинам. Например, в системах городских улиц необходимо изображать улицы с одностороннем движением. При описании систем связи между людьми или машинами необходимо учитывать существенно однонаправленные устройства. С другой стороны, введение ориентации необходимо для установления системы координат и устранения неоднозначности.
Например, при соединении электрических приборов одно направление необходимо обозначить как положительное, для того чтобы однозначно описать распределение электрического тока, хотя действительное направление может и не быть жестко ограничено.
Способы описания графа:
Выбор подходящей структуры данных для представления графа имеет принципиальное значение при разработке эффективных алгоритмов. При решении задач используются способы описания графа: матрица инцидентности графа; матрица смежности графа; списки связи и перечня ребер.
Для хранения перечня ребер необходим 2- мерный массив Х размерности 2*М. Каждая строка массива описывает одно ребро.
Пример:
l1
l2
l3
l4
V1
V2
V3

l1 V1 V3
l2 V1 V2
l3 V1 V2
l4 V2 V3
Матрица смежности – это двумерный массив А размерности N*N
1, если вершины i и j - смежные
A[i,j]=
0, если вершины i и j - несмежны

V3
V1
V2
V4
V5
V8
V7
V6
Пример: Данный граф можно представить в виде матрицы смежности:
V1 V2 V3 V4 V5 V6 V7 V8
V1 0 0 0 0 0 0 0 0
V2 1 0 0 0 0 0 0 0
V3 0 1 0 1 1 0 0 0
A= V4 0 0 0 0 1 0 0 0
V5 0 1 0 0 0 0 0 0
V6 0 0 0 0 0 0 1 1
V7 0 0 0 0 0 0 0 1
V8 0 0 0 0 0 0 0 0
Матрица инцидентности графа, имеющего n вершин и m ребер– это двумерный массив А размерности N*M
e2
e1
e3
e5
e4
e6
V3
V1
V2
V4
V5
1, если j-е ребро инцидентно i-й вершине
A[i,j]=
0, если j-е ребро неинцидентно i-й вершине.

e1 e2 e3 e4 e5 e6
v1 1 0 0 0 0 0
v2 1 1 0 0 0 1
v3 0 1 1 0 1 0
v4 0 0 1 1 0 0
v5 0 0 0 1 1 1
Алгоритм поиска в глубину
Идея метода
Просмотр вершин графа начинается с некоторой вершины v. Выбирается вершина u, смежная с v. Процесс повторяется с вершины u. Если на очередном шаге мы работаем с вершиной q и нет вершин, смежных с q и не просмотренных ранее (новых ), то возвращаемся из вершины q к вершине, из которой мы попали в q. Если это вершина v, просмотр закончен. Для фиксации признака, просмотрена вершина графа или нет, требуется структура данных типа:
Nnew: array[1..N] of boolean;
Пример
Пусть граф описан матрицей смежности A. Просмотр начинается с первой вершины. На рис. 1а приведен исходный граф, а на рис. 1б у вершин в скобках указана очередь, в которой вершины графа просматривались в процессе поиска в глубину.
1
1


(a)рис. 1 (б)
Реализация алгоритма
(Массив Nnew и A глобальные)
procedure PG(v:integer);
var j:integer;
begin
Nnew[v]:=false; write (v:3);
for j:=1 to N do
if (A[v,j]<>0) and Nnew[j] then Pg(j);
end;
Фрагмент вызывающего алгоритма
FillChar(Nnew,SizeOf(Nnew),true);
for i:=1 to N do if Nnew[i] then Pg(i);
Рассмотрим нерекурсивную реализацию этого алгоритма. А-матрица смежности; Nnew – массив признаков вершин (новая/просмотренная). Номера просмотренных вершин запоминаются в стеке St, указатель стека – переменная yk.
procedure PG1(v:integer);
var St:array[1..N] of integer;
yk:integer;
t,j:integer;
pp:boolean;
begin
FillChar (St,SizeOf (St), 0); yk:=0;
Inc(yk); St[yk]:=v; Nnnew[v]:=false;
while yk<>0 do
begin {пока стек не пуст}
t:=St[yk]; {выбор вершины из стека}
j:=0; pp:=false;
repeat
if (A[t,j+1]<>0) and Nnnew[j+1] then pp:=true else Inc(j);
until pp or (j>=N);
{найдена новая вершина или все вершины, связанные с данной, просмотренны}
if pp then
begin
Inc(yk); St[yk]:=j+1;
Nnew[j+1]:=false; {добавляем вершину в стек}
end
else Dec(yk); {убираем вершину из стека}
end;
end;
Работа алгоритма на примере графа приведенного выше. Первое обращение к PG(1).
yk St Nnew t
1 1 f t t t t t t t t 1
2 3 1 f t f t t t t t t 3
3 2 3 1 f f f t t t t t t 2
2 3 1 f f f t t t t t t 3
3 6 3 1 f f f t t f t t t 6
4 7 6 3 1 f f f t t f f t t 7
5 5 7 6 3 1 f f f t f f f t t 5
6 4 5 7 6 3 1 f f f f f f f t t 4
5 5 7 6 3 1 f f f f f f f t t 5
6 8 5 7 6 3 1 f f f f f f f f t 8
5 5 7 6 3 1 f f f f f f f f t 7
5 9 7 6 3 1 f f f f f f f f f 9
4 7 6 3 1 f f f f f f f f f 6
3 6 3 1 f f f f f f f f f 3
2 3 1 f f f f f f f f f 1
1 1 f f f f f f f f f -
0 Алгоритм поиска в ширину
Идея метода
Суть метода заключается в том, чтобы рассмотреть все вершины, связанные с текущей. Принцип выбора следующей текущей вершины таков: выбирается та, которая была раньше рассмотрена. Для реализации данного принципа необходима структура данных «очередь».
Пример
На рис.2а изображен исходный граф. На рис.2б рядом с вершинами в скобках указана очередь их просмотра.
1
1

(а) (б)
рис. 2
Процедура реализации данного метода.
procedure PW(v:integer);
var Og:array[1..N] of 0..N; {очередь}
yk1, yk2: integer; {указатели очереди, yk1 - запись; yk2 - чтение}
j:integer;
begin
FillChar(Og,SizeOf(Og),0); yk1:=0;yk2:=0; {начальная инициализация}
Inc(yk1); Og[yk1]:=v; Nnew[v]:=false; {в очередь - вершину v}
while yk2<yk1 do {пока очередь не пуста}
begin
Inc(yk2); v:=Og[yk2]; write (v:3); {берем элемент из очереди}
for j;=1 to N do {просмотр всех вершин связанных с вершиной v}
if (A[v,j}<>0) and Nnew[j] then
begin {если вершина ранее не просмотрена}
Inc(yk1); Og[yk1]:=j; Nnew:=false; {заносим ее в очередь}
end;
end;
end;
Для полноты изложения приведем реализации обоих алгоритмов, основанные на другом представлении графа — одномерном массиве списков вершин, связанных с каждой из вершин. Для этого будем использовать такую структуру данных, как динамический связанный список. Для описания графа используется массив указателей а на начала динамических списков и массив указателей на конечные элементы списков — b (последний нужен лишь для организации поиска в ширину). В основной программе может вызваться любая из описанных процедур. При поиске в ширину в очередь будут помещаться все элементы, связанные с вершиной, находящейся в начале очереди, зато за одну операцию соединения списков. Помечаться же как обработанные вершины будут лишь при удалении из очереди.
const nmax = 500;
type ptr = ^el; (указатель на элемент списка) el = record
i: integer; next: ptr end;
var a, b: array[1..nmaxJ of ptr;
vert: array[1..nmax] of boolean;
p: ptr;
i, j, k, m, n, cnt: integer;
procedure d_f_s(v: integer);
begin
vert[v] := false;
while a[v] о nil do
{пока список вершин, связанных с v, не исчерпан} begin
if vert[a[v]^.i] then d_f_s(a[v]^.i) ;
{переходим к следующему элементу списка} a[v] := a[v]^.next
end
end;
procedure b_f_s(v: integer) ;
var p,q: ptr;
begin
vert[v] := false;
p := a[v]; {указатель на начало очереди}
q := b[v]; {указатель на конец очереди}
while p о nil do {пока очередь не исчерпана}
begin
if vert[p^.i] then begin
vert[p^.i] := false;
{добавим в очередь сразу все элементы, связанные с p^.i}
q^ .next := а[р^.i];
q := b[p^.i];
end;
p := p^.next (меняем начало очереди) end;
end;
begin (основная программа)
readln(n); {n - количество вершин}
for i :=l to n do a[i] := nil ;
readin(m); {m - количество ребер}
for i := 1 to m do {считываем ребра} begin
read(j, k) ; {ребро из j в k} {добавляем элемент в список a[j]}
new (p) ;
p^.i := k;
p^.next := a[j);
if a[j] = nil then b[j] := p;
a[j] := p;
{добавляем элемент в список a(k]}
new (p) ;
p^.i := j;
p^.next := a [k] ;
if a[k] = nil then b[k] := p;
a[k] :=p end;
{структура для описания графа создана}
(метим все вершины как непосещенные}
fillchar (vert, sizeof (vert), true);
cnt :== 0;(счетчик компонент связности)
for i : = 1 to n do if vert[i] then
begin
inc(cnt) ;
d_f_s(i) end;
writein(cnt) end.
end.
Время выполнения каждой из приведенных процедур теперь составляет 0(М), то есть пропорционально количеству ребер в графе, что может дать существенный выигрыш для разреженных графов.

Приложенные файлы

  • docx 22
    Скряго
    Размер файла: 56 kB Загрузок: 1

Добавить комментарий