КУРСОВА РОБОТА НА ТЕМУ:«Реалізація алгоритмів на графах»

Зміст

 

1. Вступ………………………………………………………………3

2. Основні алгоритми на графах:…………………………………..4

    2.1 Пошук в ширину;……………………………………………..11

    2.2 Пошук в глибину;…………………………………………….13

    2.3 Топологічне сортування……………………………………..15

3. Алгоритми пошуку найкоротших шляхів з однієї вершини…17

4. Висновки…………………………………………………………31

1. Вступ

Графи зустрічаються в сотнях різних задач, і алгоритми обробки графів дуже важливі. У курсовій роботі ми розглянемо декілька основних алгоритмів обробки графів. У курсовій роботі розглядаються способи представлення графа в програмі, а також різні варіанти обходу графа (пошук в ширину і в глибину). Приводяться два застосування пошуку в глибину: топологічне сортування орієнтованого графа без циклів і розкладання орієнтованого графа в суму сильне зв’язкових компонент.

У розділах розглядається задача про найкоротші шляхи. Кожному ребру приписане деяке число, але тепер воно називається завдовжки ребра. Вимагається знайти найкоротші шляхи з однієї вершини у всі інші або найкоротші шляхи з кожної вершини в кожну. Кожне ребро розглядається як труба деякої пропускної здатності. У деякій вершині знаходиться джерело речовини, а в іншій споживач. Питається, який потік речовини можна передавати від джерела до споживача, не перевищує пропускної спроможності труб. Ця задача важлива, оскільки до неї зводиться багато цікавих задач.

2. Основні алгоритми на графах

Як зазначалося, розв’язання багатьох задач пов’язане з діями над графами: орієнтованими і неорієнтованими, циклічними і ациклічними, навантаженими і ненавантаженими. Часто такі маніпуляції вимагають від дослідника визначення вершини (вузла) або множини вершин, ребра або множини ребер, які задовольняють якійсь певній умові. Наприклад, ними можуть бути такі: знаходження множини ребер графа, значення ваги яких менше за Х; знаходження остового дерева графа, остового дерева мінімальної вартості, компонентів двозв’язності графа тощо.

Визначити такі множини можна лише шляхом систематичної перевірки всіх вершин або ребер заданого графа. Фактично задача зводиться до пошуку їх у графі. Тому важливою компонентою багатьох алгоритмів на графах є алгоритм обходу графа.

Технічні прийоми, які ми розглянемо, можна розподілити на дві категорії. До першої належать заходи реалізації класичних алгоритмів пошуку на графах методом в глибину або в ширину, до другої – заходи реалізації класичних алгоритмів на графах, в основі яких лежать обходи графа.

Процедура пошуку в ширину передбачає аналіз на кожному кроці вершин-сусідів усіх вершин, що проаналізовано спочатку (в інтерпретації прийняття рішень це означає паралельну перевірку всіх можливих альтер­натив), пошуку в глибину – першочерговий аналіз нащадків вершин, що проаналізовано останніми, тобто всі альтернативи аналізують послідовно, одна за одною; аналіз деякої альтернативи завершують лише тоді, коли є змога остаточно встановити, приводить вона до успіху чи ні. Якщо ж альтернатива призводить до невдачі, відбувається повернення і розгляд інших альтернатив.

І пошук в ширину, і пошук в глибину за досить загальних умов мають, узагалі беручи, експоненційну оцінку часової складності. Можна навести низку прикладів, коли перебір в ширину дає змогу виграти час порівняно з перебором в глибину і навпаки. Як правило, пошук в глибину дозволяє зекономити пам’ять, оскільки за його реалізації немає необхідності запам’ятовувати все дерево, достатньо зберігати в пам’яті лише вершини, що мають відношення до поточної альтернативи.

На практиці процедура пошуку в глибину набула значно більшого поширення. Можна стверджувати, що перебір з поверненням (бектрекінг) став класичною загальноінтелектуальною процедурою, яку покладено в основу сучасних методик планування цілеспрямованих дій, програмування ігор, автоматизованого доведення теорем тощо.

Враховуючи широке застосування процедур пошуку, розглянемо їх практичну реалізацію, використовуючи нотацію Паскалю. Спочатку слід задати граф, на якому працюватимуть процедури пошуку. Граф можна задати, користуючись матрицею суміжності. Реалізацію матриці суміжності за допомогою масиву описує процедура InitalizeGraph. Вважаємо, що головна програма містить такий опис:

. . .

const u = 1000; {Максимальна кількість вершин у графі}

type arr2 = array [1..n,1..n] of integer;

. . .

procedure InitalizeGraph (var B: arr2);

var m: 1..n; {Кількість вершин у графі}

i, j: 1..n; {Номери рядків і стовпців матриці}

begin

writeln(‘Введіть кількість вершин у графі m’);

read(m);

for i := 1 to m do

for j := 1 to m do

begin

writeln(‘Введіть значення елементу матриці B[‘, i, ‘, ‘, j, ‘] = ‘);

read(B[i, j]) ;

end

end;

Під час запиту на введення значення B[i,j] слід ввести 1, якщо в графі задання існує ребро, що йде із вершини з номером і у вершину з номером j, та 0 в іншому разі.

Задання графа за допомогою матриці суміжності виправдане, коли в алгоритмі пошуку превалює умова, яка обґрунтована питанням «чи існує ребро між вершинами i та j?» Кращим варіантом задання графа для алгоритмів, які б мали часову оцінку роботи, меншу за О(n2), є використання списків суміжності. У цьому разі важливим є факт орієнтовності графа. За неорієнтованого графа до списку суміжності вершини заносять всі суміжні з нею вершини. Коли ж граф орієнтований, то суміжні вершини бажано розбивати на дві групи або два списки: попередників і наступників вершини. Якщо ми маємо ребро , таке що u ® v, тоді вершина u є вершиною-попередником вершини v, а вершина v є вершиною-наступником вершини u.

Вважатимемо, що в головній програмі присутній наступний опис, який дає змогу реалізувати такий список суміжності.

type

CoreLink = ^CoreElementType; {Покажчик на CoreElement}

BindLink = ^BindElementType; {Покажчик на BindElement}

CoreElementType = record

Index: integer; {Порядковий номер}

Value: integer; {Поле для визначення відвідування} {вершин}

Prev: CoreLink; {Покажчик на наступну вершину}

Next: CoreLink; {Покажчик на попередню вершину}

Incomings: BindLink; {Покажчик на список суміжних}

{вершин (ребра входять)}

Outcomings: BindLink; {Покажчик на список вершин} {(ребра виходять)}

еnd;

BindElementType = record {Опис елементу списку суміжності}

Value: integer; {Порядковий номер}

Prev: BindLink; {Покажчик на попередній елемент} {у списку}

Next: BindLink; {Покажчик на наступний елемент}

еnd;

var

KnotNumber: integer; {Кількість вузлів у графі}

OrientationAnswer: char; {Орієнтовність графа ‘y’ or ‘n’}

Root: CoreLink; {Покажчик на початковий елемент графа}

Якщо описати дві змінні:

var CoreElement: CoreElementType;

BindElement: BindElementType;

Покажчик CoreElement↑.Next вказує на список вузлів-наступників вузла CoreElement↑.Index;

CoreElement↑.Next – на наступний вузол графа; CoreElement↑.Prev – на попередній елемент головного списку;

CoreElement↑.Incomings – на список суміжних вершин, ребра яких входять до вузла;

CoreElement↑.Outcomings – на список суміжних вершин, ребра яких виходять з вузла;

BindElement↑.Next – на наступний вузол списку суміжних вузлів; BindElement↑.Prev – на попередній.

Як іменами вершин графа скористаємося натуральними числами.

Опісля можна запропонувати процедуру InitializeGraph задання в пам’яті ЕОМ графа (неорієнтованого і орієнтованого) за допомогою динамічних змінних.

procedure InitializeGraph; {Головна процедура задання}

var NewCoreElement, CurrentCoreElement: CoreLink;

begin

CurrentCoreElement := Root; {Root вже проініціалізований заздалегідь}

repeat

New(NewCoreElement);

CurrentCoreElement^.Next := NewCoreElement;

BuildBinds(CurrentCoreElement); {Побудова списку суміжних} with NewCoreElement^ do {вершин для вузла}

begin

Index := CurrentCoreElement^.Index + 1;

Value := 0;

Prev := CurrentCoreElement;

end;

CurrentCoreElement := NewCoreElement;

until CurrentCoreElement^.Index = KnotNumber; {KnotNumber – кількість вершин у графі }

CurrentCoreElement^.Next := nil;

BuildBinds (CurrentCoreElement) ; {Побудова списку суміжних вершин для вузла}

end;

Зосередимо вашу увагу на процедурі BuildBinds, яка створює списки суміжних з вузлом вершин і в якій безпосередньо відбувається розгалуження побудови орієнтовних і неорієнтовних графів. Процедуру BuildBinds викликає процедура InitializeGraph для побудови послідовностей Binds для кожного з вузлів.

procedure BuildBinds(Nucleus: CoreLink);

var BindAnswer: char;

procedure BuildBindChain (ChainType: char; var BindRoot: BindLink);

begin {Тіло цієї процедури пропущено і описано нижче}

end;

begin

if OrientationAnswer = ‘n’ {Глобальна змінна, отримує значення}

{в головній програмі}

then {Побудова списку для неорієнтовного графа}

begin

clrscr;

writeln(‘Does not ‘, Nucleus^.Index, ‘ have ajacents?’);

repeat

BindAnswer := ReadKey;

until BindAnswer in [‘y’, ‘n’];

if BindAnswer = ‘y’ then

begin

BindAnswer := ‘a’;

BuildBindChain (BindAnswer, Nucleus^.OutComings) ;

end

else

Nucleus^.OutComings := nil;

Nucleus^.Incomings := nil;

end

else {Побудова списку для орієнтовного графа}

begin

clrscr;

writeln(‘Does not ‘, Nucleus^.Index, ‘ have incomings?’);

repeat

BindAnswer := ReadKey;

until BindAnswer in [‘y’, ‘n’];

if BindAnswer = ‘y’ then

begin

BindAnswer := ‘i’;

BuildBindChain(BindAnswer, Nucleus^.Incomings); {Побудова списку}

end

else

Nucleus^.Incomings := nil;

writeln(‘Does not ‘, Nucleus^.Index, ‘ have outcomings?’) ;

repeat

BindAnswer := ReadKey;

until BindAnswer in [‘y’, ‘n’];

if BindAnswer = ‘y’ then

begin

BindAnswer := ‘o’;

BuildBindChain (BindAnswer, Nucleus^.Outcomings);

end

else

Nucleus^.Outcomings := nil;

end;

end;

Змінну BindAnswer вводять виключно заради інтерфейсу, і вона не виконує будь-якого функціонального навантаження. Підпрограма має два відділи, які працюють залежно від орієнтованості графа (if OrientationAnswer = ‘n’ then … else …):

Якщо граф неорієнтований, то всі суміжні елементи вважають вихідними, а послідовність вхідних елементів не будують якщо граф орієнтований, то будують окремі послідовності для вхідних та вихідних вершин, хоча дані про вхідні вершини не використовують і вводять лише для можливості використання їх іншими алгоритмами обробки графа, що побудований за даною схемою.

Організація інтерфейсу для опитування користувача щодо наявності суміжних вершин є теж надлишковою та існує для можливості побудови незв’язних графів.

Така процедура викликає процедуру BuildBindChain, що описана в тілі процедури BuildBinds, для побудови послідовності BindChain, що починається з елементу, на який посилається конкретний покажчик Incomings або Outcomings елементу ядра.

Процедура BuildBindChain будує зв’язану послідовність за принципом побудови послідовності Core процедурою InitializeGraph.

Рrocedure BuildBindChain(ChainType: char; var BindRoot: BindLink);

var

i: integer;

NewBindElement, CurrentBindElement: BindLink;

begin

new(BindRoot);

BindRoot^.Prev := nil;

write(‘Enter indexes of knots ‘);

case ChainType of

‘i’: write(‘incoming into ‘);

‘o’: write(‘outcoming from ‘);

‘a’: write(‘ajacent to ‘);

end;

writeln(‘knot ‘, Nucleus^.Index, ‘ separating them with “Returns”.’);

writeln(‘Enter 0 upon completion or if there are no any.’);

CurrentBindElement := BindRoot;

repeat

readln(i);

CurrentBindElement^.Value := i;

new(NewBindElement);

CurrentBindElement^.Next := NewBindElement;

NewBindElement^.Prev := CurrentBindElement;

CurrentBindElement := NewBindElement;

until i = 0;

CurrentBindElement^.Prev^.Next := nil;

dispose(CurrentBindElement);

end;

Змінну BindAnswer, передану батьківською процедурою, використовують для створення найпростішого розгалуження в інтерфейсі.

ЗАВАНТАЖИТИ

Для скачування файлів необхідно або Зареєструватись

Реалізація алгоритмів на графах (68.6 KiB, Завантажень: 6)

Сторінка: 1 2 3
завантаження...
WordPress: 23.33MB | MySQL:26 | 0,320sec