Тема: Графи. Алгоритми обхода графів




Скачати 57.94 Kb.
НазваТема: Графи. Алгоритми обхода графів
Дата24.01.2014
Розмір57.94 Kb.
ТипДокументы
nauch.com.ua > География > Документы

http://antibotan.com/ - Всеукраїнський студентський архів

Лабораторна робота № 15

(модуль 2)

Тема: Графи. Алгоритми обхода графів. (4 години)

Мета: Ознайомити з поняттям графу. Формувати вміння і навички роботи з елементами графу засобами мови програмування Pascal.

Література:


  1. Архангельский А.Я. Язык Pascal и основы программирования в Delphi

  2. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.– М.: Мир, 1979.– 536 с.

  3. Культин Н.Б. Turbo Pascal в задачах и примерах

  4. М.С.Львов, О.В. Співаковський. Основи алгоритмізації та програмування.

  5. Марченко А.И., Марченко Л.А. Программирование в среде Turbo Pascal 7.0

  6. Меженный О.А. Turbo Pascal

  7. Н.Вирт. Алгоритмы + структуры данных = программы. Москва, Мир, 1985 г. 406 с.

  8. Н.Вирт. Алгоритмы и структуры данных. Москва, Мир, 1989 г. 420 с.

  9. Немцова Т.И., Голова С.Ю., Абрамова И.В. Программирование на языке высокого уровня. программирование на языке Object Pascal

  10. Окулов С.М. Основы программирования.– М.: ЮНИМЕДИАСТАЙЛ, 2002.– 424 с.

  11. Павловская Т.А. Паскаль. Программирование на языке высокого уровня

  12. Пильщиков В.Н. Сборник упражнений по языку Паскаль. Москва, Наука, 1989 г., 160 с.

  13. Фаронов В.В. Turbo Pascal 7.0. Начальный курс. – Учебное пособие. – М.: Издательство «ОМД Групп», 2003 г. -616 с.

  14. Фаронов В.В. Turbo Pascal 7.0. Практика программирования

  15. Фаронов В.В. 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) — алгоритм для обходу дерева, структури подібної до дерева, або графа. Робота алгоритма починається з кореня дерева (або іншої обраної вершини в графі) і здійснюється обхід в максимально можливу глибину до переходу на наступну вершину.



^

Задачі для самостійного розв’язування


  1. Неорієнтований граф заданий матрицею суміжності, яка зберігається у квадратному масиві. Виконати його прямий обхід. Результати роботи зберегти в масиві даних.

  2. Орієнтований граф заданий матрицею суміжності, яка зберігається у квадратному масиві. Виконати його прямий обхід. Результати роботи зберегти в масиві даних.

  3. Неорієнтований граф заданий матрицею суміжності, яка зберігається у квадратному масиві. Виконати його синтаксичний обхід. Результати роботи зберегти в масиві даних.

  4. Орієнтований граф заданий матрицею суміжності, яка зберігається у квадратному масиві. Виконати його синтаксичний обхід. Результати роботи зберегти в масиві даних.

  5. Неорієнтований граф заданий списком суміжності. Виконати його прямий та непрямий обходи. Результати роботи зберегти в масиві даних.

  6. Орієнтований граф заданий списком суміжності. Виконати його прямий та непрямий обходи. Результати роботи зберегти в масиві даних.

  7. Неорієнтований граф заданий списком суміжності. Виконати його синтаксичний обхід. Результати роботи зберегти в масиві даних.

  8. Орієнтований граф заданий списком суміжності. Виконати його синтаксичний обхід. Результати роботи зберегти в масиві даних.

  9. Неорієнтований граф заданий списком ребер. Виконати його синтаксичний обхід. Результати роботи зберегти в масиві даних.

  10. Орієнтований граф заданий списком ребер. Виконати його синтаксичний обхід. Результати роботи зберегти в масиві даних.

  11. Реалізувати граф. Обійти граф, використовуючи обхід в глибину. Спосіб реалізації графа: Матриця суміжності.

  12. Реалізувати програму, що вилучає задану вершину в графі.

  13. Створити програму перевода формули в постфіуксний вигляд.

  14. Реалізувати граф. Обійти граф, використовуючи обхід в ширину.

  15. Використовуючи алгоритм Флойда знайти шлях з однієї вершини в іншу зв'язкового графа

  16. Потрібно обійти всі ребра графа методом Ейлера (рекурсія).

  17. Створити програму пошуку шляху з вершини А в В.



Схожі:

Тема: Графи. Алгоритми обхода графів iconРозкладність графів. Калейдоскопічні графи
Отже, калейдоскопічні графи – це графи, що допускають калейдоскопічне розфарбування. Дамо рівносильне означення: розфарбування :...
Тема: Графи. Алгоритми обхода графів iconУрок 20 Тема: Алгоритми
Розширити й поглибити поняття “алгоритм”. Сформувати поняття “виконавець алгоритму”. Учити складати алгоритми
Тема: Графи. Алгоритми обхода графів iconЕлементи теорії графів
Графи там, де є елементи (вершини) та зв'язки між ними (ребра). Приклади – географічні схеми, комбінаційні схеми з функціональних...
Тема: Графи. Алгоритми обхода графів iconТема: Швидкі алгоритми сортування. Сортування Хоара
Мета: Закріпити поняття складності алгоритма. Сформувати вміння застосовувати швидкі алгоритми сортування
Тема: Графи. Алгоритми обхода графів iconР. М. Трохимчук збірник задач із теорії графів
Р. М. Трохимчук збірник задач із теорії графів навчальний посібник для студентів факультету кібернетики. К.: Рвц “Київський університет”,...
Тема: Графи. Алгоритми обхода графів iconРозкладність графів. Врівноважені розбиття скінченних графів
Розглянемо скінченний зв'язний граф Gr = (V,E) з множиною вершин V і множиною ребер E. Для довільних двох вершин X,yV позначимо...
Тема: Графи. Алгоритми обхода графів iconУрок 21 Тема: Алгоритми в нашому житті Цілі уроку: Розширити й поглибити...
Розвивати вміння виділяти істотні ознаки, формулювати оцінні судження, доводити правильність власного висловлення
Тема: Графи. Алгоритми обхода графів iconЛінійні алгоритми Алгоритми, в яких команди виконуються послідовно...
Алгоритми, в яких команди виконуються послідовно одна за іншою, в порядку їх запису, називаються лінійними
Тема: Графи. Алгоритми обхода графів iconТема. Жадібні алгоритми та динамічне програмування
Потім визначимо, скільки монет номіналом 10 центів не перевищить залишку від S. Ту саму операцію проведемо із монетою номіналом 5...
Тема: Графи. Алгоритми обхода графів iconТема заняття: Основні поняття теорії графів
Два з половиною століття тому в жителів тихого Кенігсберга (нині Калінінград) пропав спокій. Всі вони захопились розв'язан­­­ням...
Додайте кнопку на своєму сайті:
Школьные материалы


При копіюванні матеріалу обов'язкове зазначення активного посилання © 2013
звернутися до адміністрації
nauch.com.ua
Головна сторінка