Реализация алгоритмов на графах

Размещено на http://www.allbest.ru

3

Размещено на http://www.allbest.ru

федеральное агенство связи уральский государственный институт связи и информаТИКИ гоу впо «сибгути»

Лабораторная работа

по дисциплине

«Структуры и алгоритмы обработки данных»

Тема

Реализация алгоритмов на графах

Выполнил: Бабушкин Павел

Г. ЕКАТЕРИНБУРГ, 2012 ГОД

Содержание

Задание на курсовую работу

Анализ предметной области

Исходный код программы

Вывод

Литература

Задание на контрольную работу

граф алгоритм информация

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

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

Алгоритмы, которые необходимо реализовать на графах:

1. Определение самого короткого цикла в графе

2. Обход графа в глубину

3. Определение кратчайшего пути из заданной вершины во все остальные

4. Построение минимального остового дерева с помощью алгоритма Прима

Анализ предметной области

Для представления графа в программе была выбрана матрица смежности как самый универсальный способ представления. Для корректной работы программы в каталоге, в котором находится программа, должен находиться файл с названием “matrix.txt” в котором должна быть представлена матрица смежности графа размерностью 6*6. Возможно размещение в одном файле нескольких матриц, а затем загрузку из файла необходимой матрицы. Пример оформления матриц:

0 6 2 5 0 0

6 0 5 0 3 0

2 5 0 5 1 4

5 0 5 0 0 2

0 3 1 0 0 2

0 0 4 2 2 0

0 1 0 1 0 0

0 0 1 0 0 0

0 0 0 1 0 0

0 0 1 0 0 0

0 0 0 0 0 1

0 0 0 0 0 0

Реализованные алгоритмы:

1. Поиск самого короткого цикла в графе

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

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

2. Обход графа в глубину

Поиск в глубину является обобщением метода обхода деревьев в прямом порядке. Поиск в глубину начинается с выбора начальной вершины графа, и эта вершина помечается как посещенная. Затем для каждой вершины, смежной с текущей вершиной и ранее не посещенной, рекурсивно применяется поиск в глубину. Когда все вершины, которых можно достичь из текущей, были посещены, поиск заканчивается. Если при этом остались не посещённые вершины, то выбирается одна из них и алгоритм повторяется.

3. Построение минимального остового дерева по алгоритму Прима

Построение производится с заданной вершины по принципу нахождения минимального веса ребра от текущей вершины. Вершина начальная добавляется в остовое дерево и помечается как “пройденная”. Далее по матрице смежности находится минимальный вес ребра исходящий из этой вершины. Как только он найден, следуем по этому ребру в вершину, делаем ее текущей и также помечаем как “пройденную”. За тем повторяем весь алгоритм снова до тех пор, пока не останется не “пройденных” вершин

4. Поиск кратчайшего пути от заданной вершины до всех остальных по алгоритму Дейкстры

На первом этапе в массив кратчайших расстояний записывается вес ребра, если таковой существует от заданной вершины до остальных если же прямого пути нет то записывается “бесконечность”. На следующих этапах происходит нахождение пути от заданной вершины через все остальные по формуле: D[v]:=min(D[v],D[w]+C[w,v])

D[1..n]- массив содержащий кротчайшие пути от исходной вершины до остальных

S[]- массив(множество) посещенных вершин

w-добавленная в S вершина

Вывод

Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. -- как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут. Также графы применяются в химии, информатике и программировании, экономике, логистике и схемотехнике.

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

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

Используемая литература

1. Алексеев В.Е., Таланов В.А. Графы и алгоритмы. Структуры данных. Модели вычислений. - М.: Бином, 2006.

2. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. -- М.: Издательский дом «Вильямс», 2001.

3. Вирт Н. Алгоритмы и структуры данных. - СПб.: Невский диалект, 2008.

4. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи: Пер. с. англ. -- М.: Мир, 1982.

5. Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учебное пособие. - М.: Лаборатория базовых знаний, 2003.

6. Кнут Д. Искусство программирования для ЭВМ. Том 1: Основные алгоритмы. - М.: Мир, 1976. - 736 с. (3-е изд.: Уч. пос. - М.: Издательский дом «Вильямс», 2000.

7. Кнут Д. Искусство программирования для ЭВМ. Том 3: Сортировка и поиск. - М.: Мир, 1978. - 846 с. (2-е изд.: Уч. пос. - М.: Издательский дом «Вильямс», 2000.

8. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. -- М.: МЦНМО, 1999.

9. Красиков И.В., Красикова И.Е. Алгоритмы. Просто как дважды два. - М.: Эксмо, 2007.

10. Лэнгсам Й. Огенстайн М., Тененбаум А. Структуры данных для персональных ЭВМ. - М.: Мир, 1989.

11. Макконелл Дж. Основы современных алгоритмов. 2-е дополненное издание. - Москва: Техносфера, 2004.

12. Окулов С.М. Программирование в алгоритмах. - 2-е изд., доп. - М.: БИНОМ. Лаборатория знаний, 2006 .

13. Таха Х. Введение в исследование операций. -- М.: Издательский дом «Вильямс», 2001.

14. Ускова О.Ф. и др. Программирование алгоритмов обработки данных: Учебное пособие. - СПб: БХВ-Петербург, 2003.

Приложения

Приложение 1

Исходный код программы

uses Crt;

const

N = 6;

type

//матрица смежности

TAdMatrix = array[1..N, 1..N] of integer;

TLList = array[1..N] of boolean;

TIList = array[1..N] of integer;

var

Gr: TAdMatrix;

MOT: TIList;

//чтение графа из файла

procedure OpenFile(ind: integer; var g: TAdMatrix);

var

t: text;

i, j, tmp, m: integer;

begin

assign(t, 'matrix.txt');

reset(t);

for m:=0 to ind do

for i:=1 to n do

for j:=1 to n do

begin

read(t, tmp);

g[i,j]:=tmp;

end;

close(t);

end;

//нахождение короткого цикла

procedure Find_ShortLoop(g: TAdMatrix);

var

Ch: boolean;

L: TLLIst;

ML: Integer;

MPath: string;

function Row_IsNul(g: TAdMatrix; Row: integer): boolean;

begin

Result:=True;

for var i:=1 to N do if g[i, Row] <> 0 then Result:=False;

end;

function Col_IsNul(g: TAdMatrix; Col: integer): boolean;

begin

Result:=True;

for var i:=1 to N do if g[Col, i] <> 0 then Result:=False;

end;

function Matrix_IsNul(g: TAdMatrix): boolean;

begin

Result:=True;

for var i:=1 to N do if not Row_IsNul(g, i) then Result:=False;

end;

function Row_SetNul(var g: TAdMatrix; Row: integer): boolean;

begin

Result:=not Row_IsNul(g, Row);

for var i:=1 to N do g[i, Row]:=0;

end;

function Col_SetNul(var g: TAdMatrix; Col: integer): boolean;

begin

Result:=not Col_IsNul(g, Col);

for var i:=1 to N do g[Col, i]:=0;

end;

//функция возращает

function GetLoopLength(CurV, BaseV: integer; g: TAdMatrix; var L: TLList; CurLength: integer; CurPath: string; A: boolean): integer;

begin

//если текущая вершина есть начальная вершина, то конец

if (CurV = BaseV) and (not A) then

begin

if CurLength < ML then

begin

ML:=CurLength;

MPath:=CurPath;

end;

Result:=CurLength;

Exit;

end;

//если текущая вершина уже была посещена, то конец

if L[CurV] then

begin

Result:=-1;

Exit;

end;

//пометим текущую вершину как посещенную

L[CurV]:=True;

Result:=CurLength;

//перебираем все вершины, смежные с текущей

for var i:=1 to N do

if g[CurV, i] <> 0 then

if GetLoopLength(i, BaseV, g, L, CurLength + g[CurV, i], CurPath + '->' + IntToStr(i), false) > 0 then Result:=CurLength + g[CurV, i];

L[CurV]:=False;

end;

begin

//удалим вершины, от которых циклы не зависят

Ch:=False;

repeat

Ch:=False;

for var i:=1 to N do

begin

if Row_IsNul(g, i) then Ch:=Col_SetNul(g, i);

if Col_IsNul(g, i) then Ch:=Row_SetNul(g, i);

end;

until not Ch;

if Matrix_IsNul(g) then

begin

writeln('Данный граф ацикличен');

Exit;

end;

//среди оставшихся вершин измеряем длину мнимального цикла

ML:=1000;

for var i:=1 to N do

if not Row_IsNul(g, i) then

GetLoopLength(i, i, g, L, 0, '', true);

delete(MPath, 1, 2);

write('Самый короткий цикл в графе: ', MPath);

writeln(', длина цикла: ', ML);

writeln('');

end;

//обход графа в глубину

procedure Share_Deep(g: TAdMatrix; a: integer);

var

Visited: TLList;

Path: string;

function Row_IsVisited(g: TLList): boolean;

begin

Result:=True;

for var i:=1 to N do if not g[i] then Result:=False;

end;

procedure DepthSearch(V: integer);

begin

Path:=Path + '->' + IntToStr(V);

Visited[V]:=True;

for var i:=1 to N do

if (g[V, i] <> 0) and (not Visited[i]) then DepthSearch(i);

end;

begin

DepthSearch(a);

while not Row_IsVisited(Visited) do

for var i:=1 to N do if not Visited[i] then DepthSearch(i);

delete(Path, 1, 2);

writeln('Путь обхода: ', Path);

end;

function minf(x, y: integer): integer;

begin

if x > y then minf:=y else minf:=x;

end;

//определить кратчайший путь из заданной вершины во все остальные

procedure Path_Short(g: TAdMatrix; x: byte);

const

max = 1000000;

var

d, s, p: TIList;

min, z, k: integer;

begin

write('Введите вершину для нахождения кратчайшего пути от нее ко всем остальным: ');

readln(x);

min:=1000;

z:=1;

for var i:=1 to n do

for var j:=1 to n do

if (i <> j) and (g[i, j] = 0) then g[i,j]:=max;

for var i:=1 to n do

begin

s[i]:=0;

d[i]:=g[x,i];

p[i]:=1;

end;

s[x]:=1;

p[x]:=0;

for var i:=1 to n do

begin

for var j:=1 to n do

if (d[j] < min) and (d[j] <> 0) and (s[j] = 0) then

begin

min:=d[j];

z:=j;

end;

s[z]:=1;

for k:= 1 to n do

if s[k]=0 then

begin

d[k]:=minf(d[k], d[z] + g[z,k]);

p[k]:=k;

end;

min:=1000;

end;

for var i:=1 to n do write(i:2,' ');

write(' - Вершины графа');

writeln();

for var i:=1 to n do write(d[i]:2,' ');

write('- Кратчайшие расстояния');

writeln;

end;

//построение минимального остовного дерева

procedure OstovTree_Prim(g: TAdMatrix; var u: TIList);

var

i,j,z,min,mi,mj,f,f2,tmp: byte;

vu, u1: TIList;

begin

write('Введите вершину с которой следует начать построение: ');

readln(z);

min:=100;

f:=0;

f2:=0;

for i:=1 to n do

begin

vu[i]:=1;

u[i]:=0;

u1[i]:=0;

end;

u[z]:=1;

u1[z]:=1;

vu[z]:=0;

i:=1;

z:=2;

while z <= n - f2 do

begin

for i:=1 to n - f2 do if u1[i] = 1 then

for j:=1 to n - f2 do if (g[i, j] < min) and (g[i, j] > 0) and (u1[j] = 0) then

begin

min:=g[i,j];

mi:=i;

mj:=j;

end;

u[mj]:=z;

u1[mj]:=1;

g[mi, mj]:=0;

g[mj, mi]:=0;

inc(z,1);

min:=100;

end;

for i:=1 to n do write(i:2,' ');

writeln(' - Вершины графа');

for i:=1 to n do

begin

write(u[i]:2, ' ');

tmp:=tmp + u[i];

end;

writeln(' - Порядок их добавления в остовное дерево');

write('Суммарный вес - ',tmp);

writeln('');

end;

//вывод меню

procedure Menu;

var

MI, a: integer;

begin

writeln('');

writeln('=========================================================');

writeln('Выберите действие: ');

writeln('1. Загрузить граф из файла.');

writeln('2. Определение самого короткого цикла в графе.');

writeln('3. Выполнить обход графа в глубину.');

writeln('4. Определить кратчайший путь из заданной вершины во все остальные.');

writeln('5. Построить минимальное остовное дерево с помощью алгоритма Прима.');

writeln('6. Выход из программы.');

write('Введите номер действия: ');

readln(MI);

case MI of

1: begin write('Введите номер графа: '); readln(a); OpenFile(a, Gr); writeln('Граф загружен!'); Menu; end;

2: begin Find_ShortLoop(Gr); Menu; end; //Нахождение короткого цикла

3: begin write('Введите номер вершины, с которой необходимо начать обход: '); readln(a); Share_Deep(Gr, a); Menu; end; //Обход графа в глубину

4: begin Path_Short(Gr, 1); Menu; end; //Определение кратчайшего пути из заданной вершины во все остальные

5: begin OstovTree_Prim(Gr, Mot); Menu; end; //Построение минимального остовного дерева

6: exit;

end;

end;

begin

//загружаем файл

OpenFile(0, Gr);

//отображаем меню

Menu;

end.

Размещено на Allbest.ru