>. Однозначність -! Застосування алгоритму до одних и тихий же вихідних даних всегда винне давати одне и тієї ж результат.
. Правільність -! Застосування алгоритму до правильних вихідних даних або допустимих вихідних даних винне приводити до Отримання необхідніх результатів. Доказ правільності алгоритмом - один Із найбільш складних етапів его создания. Найбільш Поширена процедура правільності алгоритмом - це обґрунтування правомірності и перевірка правільності виконан шкірного з кроків на наборі тестів, підібраніх так, щоб охопіті всі Допустимі вхідні дані и всі Допустимі вихідні дані.
. Ефективність - алгоритм винен Забезпечувати решение Завдання за мінімальній проміжок годині з мінімальнімі витратами пам'яті. Для ОЦІНКИ алгоритмів існує много крітеріїв. Найчастіше оцінка алгоритму Полягає в оцінці годин витрат на вирішенню Завдання в залежності від «розміру» вихідних даних. Вікорістовується такоже Термін, тимчасова здатність и «трудомісткість алгоритму». Фактично ця оцінка зводу до ОЦІНКИ кількості основних операцій, Які віконуються алгоритмами, оскількі Кожна конкретна операція віконується за кінцевій Заздалегідь відомій годину.
Алгоритм вирішенню задачі виходим більш ефективного, если користуватись методами покрокової розробки, суть которого Полягає в тому, что алгоритм розробляється «зверху вниз». Спочатку візначається загальний ПІДХІД до вирішенню Завдання, потім віділяються ОКРЕМІ самостійні части, Які віконують якусь кінцеву Обробка даних. Кожна Із віділеніх частин у свою черго может розбіватіся на ОКРЕМІ части. Такий ПІДХІД дозволяє Розбита алгоритм на части (модулі), шкірні з якіх вірішує самостійну підзадачу. Коженая з модулів реалізується у виде окремої процедуру або Функції. Тоді решение задачі складається з послідовного виклику процедур. Програма, что реалізує такий алгоритм, назівається структурованою програмою.
. 2 Визначення та спосіб представлення графів
граф алгоритм мова програмування
Перш за все, дамо формально визначення та способи представлення графів. З формальної точки зору граф є впорядкованим парою
=(V, Е) (1.1)
множини, перше з якіх складається з вершин, або вузлів, графа, а друга - з его ребер. Ребро зв язує между собою две вершини. При роботі з графами нас часто цікавить, як прокласті шлях з ребер від однієї вершини графа до Іншої. Тому ми говорітімемо про рух по ребру; це означає, что ми Переходимо з вершини А графа в іншу вершину В, пов язану з нею ребром АВ (ребро графа, что зв'язує две вершини, содержания позначається цією парою вершин). У цьом випадка ми говоримо, что А прімікає до В, или что ЦІ две вершини сусідні.
Як правило, две вершини, пов'язані между собою ребром, рівноправні, и самє того Такі графи назіваються неорієнтованімі: немає ніякої різниці между качаном и кінцем ребра. Ребра неорієнтованого графа, Частіше Усього званого просто графом, можна проходити в обох безпосередньо. У цьом випадка ребро - це неврегульована пара вершин, его кінців. У орієнтованому графові, или орграфі, ребра є впорядкованим парами вершин: перша вершина - це качан ребра, а друга - его Кінець. Далі ми содержания говорітімемо просто про ребра, а орієнтовані смороду або ні буде зрозуміле з контексту. Приклада Існування графів в оточуючому нас середовіщі наведено у табліці 1.1
Таблиця 1.1 - прикладом неорієнтованіх графів
ГрафВершініРебраСім яЛюдіРодінні звraquo;язкиМістоПерехрестяВулиціМережаКомп'ютериКабеліБудинокКвартириСусідствоМетроСтанціїПересадкиЛисток в клітінкуКлітінкіНаявність Загальної Межі
Для візуального представлення графа его малюють, а не задають їх множини. Вершини зображуватімемо кружечками, а ребра - відрізкамі ліній. Усередіні кружечків запісані Мітки вершин. Ребра орієнтованого графа забезпечуються стрілкамі, что вказують допустимі направление руху по ребру. На малюнку 1.1 зображено графічне представлення неорієнтованого (а), орієнтованого (б) i взваженного (в) графу.
а) б)
в)
Малюнок 1.1 - Приклад зображення графів
У графі Важлива только факт наявності зв язку между двома вершинами. Від способу зображення цього зв язку структура графа НЕ поклади. Например, три графи на рис. 1.2 співпадають, а два графи на рис. 1.3 - Різні.
Малюнок 1.2 - Три способу зображення одного графа
Малюнок 1.3 - Приклад двох різніх графів
З наведеного вищє визначення вітікає, что в класичності графах НЕ буває петель - ребер, что сполучають Деяк вершину саму з собою (рис. 1.4). Крім того, в класичному графові НЕ був...
