Лабораторна робота № 15
(модуль 2)
Тема: Графи. Алгоритми обхода графів. (4 години)
Мета: Ознайомити з поняттям графу. Формувати вміння і навички роботи з елементами графу засобами мови програмування Pascal.
Література:
Архангельский А.Я. Язык Pascal и основы программирования в Delphi
Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.– М.: Мир, 1979.– 536 с.
Культин Н.Б. Turbo Pascal в задачах и примерах
М.С.Львов, О.В. Співаковський. Основи алгоритмізації та програмування.
Марченко А.И., Марченко Л.А. Программирование в среде Turbo Pascal 7.0
Меженный О.А. Turbo Pascal
Н.Вирт. Алгоритмы + структуры данных = программы. Москва, Мир, 1985 г. 406 с.
Н.Вирт. Алгоритмы и структуры данных. Москва, Мир, 1989 г. 420 с.
Немцова Т.И., Голова С.Ю., Абрамова И.В. Программирование на языке высокого уровня. программирование на языке Object Pascal
Окулов С.М. Основы программирования.– М.: ЮНИМЕДИАСТАЙЛ, 2002.– 424 с.
Павловская Т.А. Паскаль. Программирование на языке высокого уровня
Пильщиков В.Н. Сборник упражнений по языку Паскаль. Москва, Наука, 1989 г., 160 с.
Фаронов В.В. Turbo Pascal 7.0. Начальный курс. – Учебное пособие. – М.: Издательство «ОМД Групп», 2003 г. -616 с.
Фаронов В.В. Turbo Pascal 7.0. Практика программирования
Фаронов В.В. Turbo Pascal 7.0. Учебный курс
Короткі теоретичні відомості.

Граф утворюють кілька записів, покажчики яких виставлені довільним чином.
Існує досить велике число різноманітних способів представлення графів. Проте ми згадаємо тут тільки найкорисніші з погляду програмування: матриця суміжності, список ребер та список суміжності..
Матриця суміжності Sm - це квадратна матриця розміром NXN (N - кількість вершин в графі), заповнена одиницями і нулями за наступним правилом: якщо в графі є ребро e, що сполучає вершини u і v, то Sm[u,v]= 1, інакше Sm[u,v]= 0.
Відмітимо, що дане визначення підходить як орієнтованим, так і неорієнтованим графам: матриця суміжності для неорієнтованого графа буде симетричною щодо своєї головної діагоналі, а для орграфу - несиметричною.
Задати зважений граф за допомогою матриці суміжності теж можливо. Необхідно лише внести невелику зміну до визначення: якщо в графі є ребро e, що сполучає вершини u і v, то Sm[u,v]= ves(e), інакше Sm[u,v]= 0.
Зручність матриці суміжності полягає в наочності і прозорості алгоритмів, заснованих на її використанні. А незручність - в декілька завищеній вимозі до пам'яті: якщо граф далекий від повного, то в масиві, що зберігає матрицю суміжності, виявляється багато "порожніх місць" (нулів). Крім того, для "спілкування" з користувачем цей спосіб представлення графів не дуже зручний: його краще застосовувати тільки для внутрішнього представлення даних.
Список ребер є досить зручним способом для зовнішнього представлення вхідних даних. Нехай кожен рядок вхідного файлу містить інформацію про одне ребро (дузі):
<номер_початкової_вершини> <номер_кінцевої_вершини> [<вага_ребра>]
Якщо задається орієнтований граф, то номери вершин розуміються як впорядкована пара, а якщо граф неорієнтований - як неврегульована.
Спосіб завдання графів списками суміжності має на увазі, що для кожної вершини буде вказаний список всіх суміжних з нею вершин (для орграфу - список вершин, витікаючих дуг, що є кінцями). Конкретний формат вхідного файлу, що містить списки суміжності, необхідно обговорити окремо. Наприклад, в нашому випадку початкова вершина відокремлена від списку суміжності двокрапкою:
<номер_початкової_вершини>: <номери_суміжних_вершин>
Найприродніше застосовувати цей спосіб для завдання орграфів, проте і для решти варіантів він теж підходить.
Власне, цей спосіб представлення графів є всього лише внутрішньою реалізацією списку суміжності: у одному лінійному списку містяться номери "початкових вершин", а в останніх - номери суміжних вершин або покажчики на ці вершини.
type uk_versh = ^vershina;
uk_duga = ^duga
vershina = record number : integer;
sled_vershina : uk_versh;
spisok_dug : uk_duga
end;
duga = record konec_dugi : uk_versh;
sled_duga : uk_duga;
end;
Очевидна перевага такого способу представлення графів полягає в економічному використанні пам'яті. І навіть невелика надмірність даних, до якої доводиться вдаватися у разі неорієнтованого графа, задаючи кожне ребро як дві дуги, окуповується гнучкістю всієї структури, що особливо зручно при необхідності частих перестроювань в процесі роботи програми.
Якщо в приведені описи типів даних додати поля, які могли б зберігати ваги вершин і дуг, то таким же способом можна задавати і зважені графи (орграфи).
Пошук у ширину
Якщо задано граф G = (V, E) та початкову вершину s, алгоритм пошуку в ширину систематично обходить всі досяжні із s вершини. На першому кроці вершина s позначається, як пройдена, а в список додаються всі вершини, досяжні з s без відвідування проміжних вершин. На кожному наступному кроці всі поточні вершини списку відмічаютсья, як пройдені, а новий список формується із вершин, котрі є ще не пройденими сусідами поточних вершин списку. Для реалізації списку вершин найчастіше використовуєтьсячерга. Виконання алгоритму продовжується до досягнення шуканої вершини або до того часу, коли на певному кроці в список не включається жодна вершина. Другий випадок означає, що всі вершини, доступні з початкової, уже відмічені, як пройдені, а шлях до цільової вершини не знайдений.
Алгоритм має назву пошуку в ширину, оскільки «фронт» пошуку (між пройденими та непройденими вершинами) одноманітно розширюється вздовж всієї своєї ширини. Тобто, алгоритм проходить всі вершини на відстані k перед тим як пройти вершини на відстані k+1.

Пошук в глибину
Алгори?тм пошуку? в глибину? (англ. Depth-first search, DFS) — алгоритм для обходу дерева, структури подібної до дерева, або графа. Робота алгоритма починається з кореня дерева (або іншої обраної вершини в графі) і здійснюється обхід в максимально можливу глибину до переходу на наступну вершину.

Задачі для самостійного розв’язування
Неорієнтований граф заданий матрицею суміжності, яка зберігається у квадратному масиві. Виконати його прямий обхід. Результати роботи зберегти в масиві даних.
Орієнтований граф заданий матрицею суміжності, яка зберігається у квадратному масиві. Виконати його прямий обхід. Результати роботи зберегти в масиві даних.
Неорієнтований граф заданий матрицею суміжності, яка зберігається у квадратному масиві. Виконати його синтаксичний обхід. Результати роботи зберегти в масиві даних.
Орієнтований граф заданий матрицею суміжності, яка зберігається у квадратному масиві. Виконати його синтаксичний обхід. Результати роботи зберегти в масиві даних.
Неорієнтований граф заданий списком суміжності. Виконати його прямий та непрямий обходи. Результати роботи зберегти в масиві даних.
Орієнтований граф заданий списком суміжності. Виконати його прямий та непрямий обходи. Результати роботи зберегти в масиві даних.
Неорієнтований граф заданий списком суміжності. Виконати його синтаксичний обхід. Результати роботи зберегти в масиві даних.
Орієнтований граф заданий списком суміжності. Виконати його синтаксичний обхід. Результати роботи зберегти в масиві даних.
Неорієнтований граф заданий списком ребер. Виконати його синтаксичний обхід. Результати роботи зберегти в масиві даних.
Орієнтований граф заданий списком ребер. Виконати його синтаксичний обхід. Результати роботи зберегти в масиві даних.
Реалізувати граф. Обійти граф, використовуючи обхід в глибину. Спосіб реалізації графа: Матриця суміжності.
Реалізувати програму, що вилучає задану вершину в графі.
Створити програму перевода формули в постфіуксний вигляд.
Реалізувати граф. Обійти граф, використовуючи обхід в ширину.
Використовуючи алгоритм Флойда знайти шлях з однієї вершини в іншу зв'язкового графа
Потрібно обійти всі ребра графа методом Ейлера (рекурсія).
Створити програму пошуку шляху з вершини А в В.