Дипломная (вкр): Алгоритми на графах та їх практичне застосування

) a ;

) b, d ;

) b, d, c ( шляхи adb, abd, abc );

) c ( шлях adbc ).

Відстань між вершинами u і v - це довжина найкоротшого шляху від u до v. З цього визначення видно, що відстань між вершинами a і c в на рисунку 1.2 рівне 2.

Цикл - це замкнутий шлях. Усі вершини в циклі, окрім першої і останньої, мають бути різні. Наприклад, циклом є шлях abda в графі на рисунку 1.2.

Ейлеров граф - це граф, в якому існує шлях або цикл, що містить усі ребра графа (вершини можуть повторюватися). Наприклад, граф на рисунку 1.6 є Ейлеровым: шуканим шляхом в нім буде dbacfbcd.

Рисунок 1.6 - Граф Эйлера

Гамільтоновий граф - це граф, в якому існує шлях або цикл (без повторень ребер), що містить усі вершини графа. Наприклад, на рисунку 1.6 шуканий цикл: abdfca.

Існує досить велике число різноманітних способів представлення графів. Проте ми викладемо тут тільки найкорисніші з точки зору програмування.

Матриця суміжності Sm - це квадратна матриця розміром NxN (N - кількість вершин в графі), заповнена одиницями і нулями за наступним правилом: якщо в графі є ребро, що сполучає вершини u і v, то Sm[u, v] = 1, інакше Sm[u, v] = 0.

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

Задати зважений граф за допомогою матриці суміжності теж можливо. Необхідно лише внести невелику зміну до визначення: якщо в графі є ребро e, що сполучає вершини u і v, то Sm[u, v] = ves(e), інакше Sm[u, v] = 0. Таким чином, незважений граф можна інтерпретувати як зважений, усі ребра якого мають однакову вагу 1. Невелике утруднення виникне у тому випадку, якщо в графі дозволяються ребра з вагою 0. Тоді доведеться зберігати два масиви: один з нулями і одиницями, які служать показником наявності ребер, а другий - з вагами цих ребер.

Зручність матриці суміжності полягає в наочності і прозорості алгоритмів, заснованих на її використанні. А незручність - в дещо завищеній вимозі до пам'яті: якщо граф далекий від повного, то в масиві, що зберігає матрицю суміжності, виявляється багато "порожніх місць" (нулів). Крім того, для "спілкування" з користувачем цей спосіб представлення графів не занадто зручний: його краще застосовувати тільки для внутрішнього представлення даних.

Інший спосіб завдання графів полягає у використанні списку ребер. Цей спосіб завдання графів найбільш зручний для зовнішнього представлення вхідних даних. Зазвичай його представляють у вигляді: <номер_початкової_вершини> <номер_кінцевої_вершини> [<вага_ребра>]. Якщо задається орієнтований граф, то номери вершин розуміються як впорядкована пара, а якщо граф неорієнтований - як неврегульована.

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

.3 Огляд програмних засобів

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

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

Блок-схеми можна розглядати як графічну альтернативу псевдокоду. На відміну від стандартизації синтаксису мов програмування, на синтаксис псевдокоду зазвичай не встановлюється стандартів, так як останній безпосередньо не компілюють у виконувану програму. Тому можна сказати, що зазвичай кожен варіант використання псевдокоду може бути відмінним від попередньо відомих, однак щоб бути максимально зрозумілим, намагаються використовувати більш-менш сталі форми його запису, як правило, запозичені з будь-якої мови програмування. Найчастіше джерелом псевдокоду служать кілька мов, і таким чином псевдокод часто не містить специфічних ознак кожної мови програмування. Крім того, математичні вирази часто включаються в псевдокод в тому вигляді, як їх прийнято записувати в математиці, а не в мовах програмування, а деякі фрагменти псевдокоду можуть записуються фразами природної мови (російської, англійської і т.д.). Однак при цьому конструкції деяких мов програмування частіше використовуються для псевдокоду. Так, наприклад, дуже часто використовується синтаксис, схожий на синтаксис мови Pascal. Це пояснюється тим, що Pascal створювався як мова, орієнтована на задачі навчання програмування, і тому синтаксис цієї мови особливо пристосований для сприйняття людиною. Часто використовуються і інші мови: C, Algol, Fortran та інші.

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

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

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

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

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

Приклади: C++, Visual Basic, Java, Python, Ruby, Perl, Delphi (Pascal), PHP. Мовам високого рівня властиве вміння працювати з комплексними структурами даних. У більшість із них інтегрована підтримка рядкових типів, об’єктів, операцій файлового вводу-виводу і т. п.

Наведемо основні можливості мов програмування для роботи з графами. Насамперед це алгоритмічні конструкції циклів та умовний оператор.

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

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

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

Іноді в програмах використовуються цикли, вихід з яких не передбачено логікою програми. Такі цикли називаються безумовними, або нескінченними. Спеціальних синтаксичних засобів для створення нескінченних циклів, з урахуванням їх нетиповості, мови програмування не передбачають, тому такі цикли створюються за допомогою конструкцій, призначених для створення звичайних (або умовних) циклів. Для забезпечення нескінченного повторення перевірка умови в такому циклі або відсутня (якщо дозволяє синтаксис, як, наприклад, у циклі LOOP… END LOOP мови Ада), або замінюється константним значенням (while true do… в Паскаль).

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

Цикл з післяумовою - цикл, в якому умова перевіряється після виконання тіла циклу. Звідси випливає, що тіло завжди виконується хоча б один раз. У мові Паскаль цей цикл реалізує оператор repeat. until, у Сі - do… while.

У трактуванні умови циклу з післяумовою в різних мовах є деякі розбіжності. У Паскаль і мовах, що пішли від нього, умова такого циклу трактується як умова виходу (цикл завершується, коли умова істинна, «цикл до»), а в Сі і його нащадках - як умова продовження (цикл завершується, коли умова хибна, такі цикли іноді називають «цикл поки»).

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

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

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

Частина мов програмування містять спеціальні конструкції для організації циклу з виходом із середини. Так, в мові VB.Net для цього використовується конструкція Do… LOOP і команда виходу EXIT DO:

Do { While | Until } условие

[ Частина тіла циклу ]

Частина тіла циклу<умова вихода> [ Exit Do ]

[ Частина тіла циклу ]

Тут всередині циклу може бути будь-яка кількість команд виходу.

У тих мовах, де подібних конструкцій не передбачено, цикл з виходом із середини може бути змодельовано за допомогою будь-якого умовного циклу і оператора дострокового виходу з циклу (такого, як break в Сі), або оператора безумовного переходу goto.

Цикл з лічильником - цикл, в якому деяка змінна змінює своє значення від заданого початкового значення до кінцевого значення з деяким кроком, і для кожного значення цієї змінної тіло циклу виконується один раз. У більшості процедурних мов програмування реалізується оператором for, в якому вказується лічильник (так звана «змінна циклу»), необхідна кількість проходів (або граничне значення лічильника) і, можливо, крок, з яким змінюється лічильник.

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

У деяких мовах, наприклад, Сі та інших, що пішли від неї, цикл for, незважаючи на синтаксичну форму циклу з лічильником, насправді є циклом з передумовою. Тобто в конструкції for спочатку пишеться довільна ініціалізація циклу, а потім - умова продовження і, нарешті, деяка операція, яка виконується після кожного тіла циклу (це не обов’язково має бути зміна лічильника; це може бути правка покажчика або яка-небудь зовсім стороння операція). Для мов такого виду вищеописана проблема вирішується дуже просто: змінна-лічильник поводиться абсолютно передбачувано і по завершенні циклу зберігає своє останнє значення.

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

Повне число виконань тіла внутрішнього циклу не перевищує добутку числа ітерацій внутрішнього і всіх зовнішніх циклів. Наприклад взявши три вкладених один в одного цикли, кожен по 10 ітерацій, отримаємо 10 виконань тіла для зовнішнього циклу, 100 для циклу другого рівня і 1000 в самому внутрішньому циклі.

Одна з проблем, пов’язаних з вкладеними циклами - організація дострокового виходу з них. У багатьох мовах програмування є оператор дострокового завершення циклу (break в Сі, exit в VB.Net, last в Perl і т. п.), але він, як правило, забезпечує вихід тільки з циклу того рівня, звідки викликаний. Виклик його з вкладеного циклу призведе до завершення тільки цього внутрішнього циклу, зовнішній же цикл продовжить виконуватися. Проблема може здатися надуманою, але вона дійсно іноді виникає при програмуванні складної обробки даних, коли алгоритм вимагає негайного переривання в певних умовах, наявність яких можна перевірити тільки в глибоко вкладеному циклі.

Рішень проблеми виходу з вкладених циклів кілька.

      Найпростіший - використовувати оператор безумовного переходу goto для виходу в точку програми, безпосередньо наступної за вкладеним циклом. Цей варіант критикується прихильниками структурного програмування, як і всі конструкції, що вимагають використання goto. Деякі мови програмування, наприклад Modula-2, просто не мають оператора безумовного переходу, і в них подібна конструкція неможлива.

      Альтернатива - використовувати штатні засоби завершення циклів, у разі необхідності встановлюючи спеціальні прапори, які потребують негайного завершення обробки. Недолік - ускладнення коду, зниження продуктивності без будь-яких переваг, крім теоретичної «правильності» із-за відмови від goto.

      Розміщення вкладеного циклу в процедурі. Ідея полягає в тому, щоб вся дії, що можливо знадобитися перервати достроково, оформлюється у вигляді окремої процедури, і для дострокового завершення використовувати оператор виходу з процедури (якщо такий є в мові програмування). У Сі, наприклад, можна побудувати функцію з вкладених циклом, а вихід з неї організувати за допомогою оператора return. Недолік - виділення фрагмента коду в процедуру не завжди логічно обґрунтовано, і не всі мови мають штатні засоби дострокового завершення процедур.