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

 

ЗМІСТ

ВСТУП

. Загальний огляд проблеми та обґрунтування вибору програмних засобів

.1 Значення алгоритмів на графах

.2 Визначення та способи представлення графів

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

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

.1 Пошук завширшки

.2 Пошук в глибину

.3 Побудова мінімального остового дерева. Алгоритм Прима

.4 Алгоритм Дейкстри

.5 Модель Флойда-Уоршалла

. Програмна реалізація алгоритмів

.1 Огляд можливостей мови програмування

.2 Опис функцій програмної моделі

.3 Інтерфейс програми

ВИСНОВКИ

ПЕРЕЛІК ВИКОРИСТАНИХ ДЖЕРЕЛ

ВСТУП

Спробуйте намалювати „заклеєний конверт одним розчерком пера, тобто не відриваючи ручки від паперу й не проводячи двічі один і той самий відрізок. Такого роду запитання з давніх-давен цікавили математиків.

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

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

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

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

Для досягнення поставленої мети в роботі вирішені наступні задачі:

розглянуті і проаналізовані підходи до рішення задачі;

обґрунтовано вибір технічних засобів для рішень завдань;

визначені основні поняття теорії графів та засоби їх представлення у компютерних програмах;

визначена структура даних для вирішення поставленої задачі;

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

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

Предметом дослідження є застосування теорії графів при розвязанні завдань різних видів та вивчення елементів теорії графів.

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

У першому розділі розглянуто коло питань пов'язаних з формальним визначенням, способами подання графів та обґрунтовується вибір програмних засобів.

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

У третьому розділі наведено програмну реалізацію алгоритмів та можливості мови програмування Visual Basic .Net, які є вирішальними при програмуванні алгоритмів.

Отримані результати можуть бути впроваджені в практику Горлівського регіонального інституту під час вивчення змістовного модуля «Теорія графів».

1. Загальний огляд проблеми та обґрунтування вибору програмних засобів

.1 Значення алгоритмів на графах

Передусім, декілька слів про те, як виникає поняття графа з природних умов завдань. Наведемо декілька прикладів.

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

Аналогічно, можна розглянути вулиці і перехрестя усередині одного міста. Помітимо, що можуть бути вулиці з одностороннім рухом.

Мережа комп'ютерів, сполучених дротяними лініями зв'язку.

Набір слів, кожне з яких починається на певну букву і закінчується на цю ж або іншу букву.

Множина кісток доміно. Кожна кістка має 2 числа: ліву і праву половину кістки.

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

Генеалогічні дерева, що вказують споріднені стосунки між людьми.

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

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

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

Родоначальником теорії графів прийнято вважати Леонарда Ейлера, який у 1736 році розвязавши життєву задачу про Кенігсберзькі мости, встановив властивості звязаного графа та зробив деякі загальні висновки.

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

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

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

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

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

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

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

Основні властивості алгоритму:

. Масовість - алгоритм повинен бути застосований для цілого класу однотипних задач ;

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

. Результативність - по закінченні роботи алгоритму повинен бути отриманий певний результат.

. Однозначність - застосування алгоритму до одних і тих же вихідних даних завжди повинно давати один і той же результат.

. Правильність - застосування алгоритму до правильних вихідних даних або допустимих вихідних даних повинно приводити до отримання необхідних результатів. Доказ правильності алгоритму - один із найбільш складних етапів його створення. Найбільш поширена процедура правильності алгоритму - це обґрунтування правомірності і перевірка правильності виконання кожного з кроків на наборі тестів, підібраних так, щоб охопити всі допустимі вхідні дані і всі допустимі вихідні дані.

. Ефективність - алгоритм повинен забезпечувати рішення завдання за мінімальний проміжок часу з мінімальними витратами пам'яті. Для оцінки алгоритмів існує багато критеріїв. Найчастіше оцінка алгоритму полягає в оцінці часових витрат на вирішення завдання в залежності від «розміру» вихідних даних. Використовується також термін, тимчасова здатність і «трудомісткість алгоритму». Фактично ця оцінка зводиться до оцінки кількості основних операцій, які виконуються алгоритмами, оскільки кожна конкретна операція виконується за кінцевий заздалегідь відомий час.

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

.2 Визначення та способи представлення графів

граф алгоритм мова програмування

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

= (V, Е) (1.1)

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

Як правило, дві вершини, пов'язані між собою ребром, рівноправні, і саме тому такі графи називаються неорієнтованими: немає ніякої різниці між "початком" і "кінцем" ребра. Ребра неорієнтованого графа, частіше усього званого просто графом, можна проходити в обох напрямах. В цьому випадку ребро - це неврегульована пара вершин, його кінців. У орієнтованому графові, або орграфі, ребра є впорядкованими парами вершин : перша вершина - це початок ребра, а друга - його кінець. Далі ми скорочено говоритимемо просто про ребра, а орієнтовані вони або ні буде зрозуміле з контексту. Приклади існування графів в оточуючому нас середовищі наведено у таблиці 1.1

Таблиця 1.1 - Приклади неорієнтованих графів

ГрафВершиниРебраСім'яЛюдиРодинні зв'язкиМістоПерехрестяВулиціМережаКомп'ютериКабеліБудинокКвартириСусідствоМетроСтанціїПересадкиЛисток в клітинкуКлітинкиНаявність загальної межі

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

а)б)

в)

Рисунок 1.1 - Приклад зображення графів

У графі важливий тільки факт наявності зв'язку між двома вершинами. Від способу зображення цього зв'язку структура графа не залежить. Наприклад, три графи на рис. 1.2 співпадають, а два графи на рис. 1.3 - різні.

Рисунок 1.2 - Три способу зображення одного графа

Рисунок 1.3 - Приклад двох різних графів

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

Рисунок 1.4 -Псевдограф

Ребро е і вершина v називаються інцидентними один одному, якщо вершина v є одним з кінців ребра е.тБудь-якому ребру інцидентно рівно дві вершини, а ось вершині може бути інцидентно довільна кількість ребер, це кількість і визначає міра вершини. Ізольована вершина взагалі не має інцидентних нею ребер (її міра дорівнює 0 ).

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

Шлях в графі це послідовність вершин (без повторень), в які будь-які дві сусідні вершини суміжні. Наприклад, в графові, зображеному на рисунку 1.2, є два різні шляхи з вершини a в вершину с: adbc та abc. Вершина v досяжна з вершини u, якщо існує шлях, що починається в u та що закінчується в v. Граф називається зв'язним, якщо усі його вершини взаємно досяжні.

Компонента звязності - це максимальний зв'язний підграф. У загальному випадку граф може складатися з довільної кількості компонент зв'язності. Помітимо, що будь-яка изолированнаявершина є окремою компонентою зв'язності. На рисунку 1.5 зображений граф, що складається з чотирьох компонент зв'язності: [abhk], [gd], [c]і [f].

Довжина шляху - кількість ребер, з яких цей шлях складається. Наприклад, довжина вже згаданих шляхів adbc і abc (див. рис. 1.2) - 3 і 2 відповідно.

Рисунок 1.5 - Незвязний граф

Говорять, що вершина v належить k -му рівню відносно вершини u, якщо існує шлях з u в v довжиною рівно k ребер. Одна і та ж вершина може відноситися до різних рівнів. Наприклад, в графові, зображеному на рисунку 1.2, відносно вершини a існує 4 рівні:

) 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. Мовам високого рівня властиве вміння працювати з комплексними структурами даних. У більшість із них інтегрована підтримка рядкових типів, обєктів, операцій файлового вводу-виводу і т. п.

Першою мовою програмування високого рівня вважається компютерна мова Plankalkül розроблена німецьким інженером Конрадом Цузе ще в період 1942-1946 рр. Однак, широке застосування високорівневих мов почалося з виникненням ФОРТРАН і створенням компілятора для цієї мови (1957).

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

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

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

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

Іноді в програмах використовуються цикли, вихід з яких не передбачено логікою програми. Такі цикли називаються безумовними, або нескінченними. Спеціальних синтаксичних засобів для створення нескінченних циклів, з урахуванням їх нетиповості, мови програмування не передбачають, тому такі цикли створюються за допомогою конструкцій, призначених для створення звичайних (або умовних) циклів. Для забезпечення нескінченного повторення перевірка умови в такому циклі або відсутня (якщо дозволяє синтаксис, як, наприклад, у циклі 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. Недолік - виділення фрагмента коду в процедуру не завжди логічно обґрунтовано, і не всі мови мають штатні засоби дострокового завершення процедур.

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

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

Ще одним варіантом циклу є цикл, який задає виконання певної операції для обєктів з заданого множини, без явної вказівки порядку перерахування цих обєктів. Такі цикли називаються спільними (а також циклами по колекції, циклами перегляду) і являють собою формальний запис інструкції виду: «Виконати операцію X для всіх елементів, що входять в безліч M». Спільний цикл, теоретично, ніяк не визначає, в якому порядку операція буде застосовуватися до елементів множини, хоча певні мови програмування, зрозуміло, можуть задавати конкретний порядок перебору елементів. Довільність дає можливість оптимізації виконання циклу за рахунок організації доступу не в заданому програмістом, а в найбільш вигідному порядку. При наявності можливості паралельного виконання декількох операцій можливо навіть паралельне виконання спільного циклу, коли одна й та сама операція одночасно виконується на різних обчислювальних модулях для різних обєктів, при тому що логічно програма залишається послідовною.

Спільні цикли є в деяких мовах програмування (VB.Net, C #, Java, JavaScript, Perl, Python, PHP, LISP, Tcl та ін) - вони дозволяють виконувати цикл по всім елементам заданої колекції обєктів. У визначенні такого циклу потрібно вказати тільки колекцію обєктів та змінну, якій в тілі циклу буде присвоєно значення обєкту, який в даний момент обробляється (або посилання на нього). Синтаксис в різних мовах програмування синтаксис оператора різний, але в мові VB.Net мае наступний синтаксис:Each element [ As datatype ] In group

[ statements ]

[ Exit For ]

[ statements ][ element ]

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

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

Оператори, які виконують роль розгалуження програми на підставі якої-небудь умови, називаються операторами умовного переходу.

Найпростішими операторами умовного переходу є оператори Ifумова Then [ Оператори 1 ] [ Else [ Оператори 2 ] ]

Умовою завжди має бути логічний вираз (тобто результат якого або true або false). Після ключового слова Then пишуться оператори, які виконуються, якщо умова істинна, після ключового слова Else пишуться оператори, які виконуються, якщо умова хибна. Частина else є необовязковою, якщо вона відсутня, то якщо умова хибна, буде виконуватися наступний за if оператор.

Виходячи з поставлених вимог для розробки модуля реалізації алгоритмів на графах з візуалізацією етапів розробки доцільно для розробки використати Object-технологію - інтерфейс користувача розробити в середовищі програмування Visual Studio 2010, використовуючи мову програмування Visual Basic .Net.

Платформа Microsoft. NET надає:

?Стійке середовище виконання CLR (Common Language Runtime), яке входить до складу даної платформи;

?Засоби розробки додатків на будь-якій з багатьох мов програмування, що підтримуються платформою.NET;

?Величезну бібліотеку класів NET Framework, що лежить в основі відкритої моделі програмування. Вони доступні в будь-якій мові програмування, що підтримується платформою.NET;

?Підтримку мережевої інфраструктури, побудованої на верхньому рівні стандартів Internet, внаслідок чого забезпечується високий рівень взаємодії між додатками;

?Підтримку нового промислового стандарту, а саме технології Web-служб. Технологія Web-служб надає новий механізм створення розподілених додатків. По суті, вона є поширенням технології створення додатків на базі компонентів і на сферу Internet;

?Модель безпеки, що програмісти можуть легко використовувати у своїх програмах;

?Потужні інструментальні засоби розробки.

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

.1 Пошук завширшки

Пошук завширшки (breadth-first search)є одним з простих алгоритмів для обходу графа і є основою для багатьох важливих алгоритмів для роботи з графами. Наприклад, алгоритм Прима (Prim) пошуку мінімального остовного дерева або алгоритм Дейкстры (Dijkstra) пошуку найкоротшого шляху з однієї вершини використовують ідеї, схожі з ідеями, використовуваними при пошуку завширшки.

Пошук завширшки був формально запропонований Э. Ф. Муром в контексті пошуку шляху в лабіринті. Лі незалежно відкрив той же алгоритм в контексті розводки провідників на друкованих платах.

Пошук завширшки може застосовуватися для вирішення завдань, пов'язаних з теорією графів, :

хвилевий алгоритм пошуку шляху в лабіринті (алгоритм Лі);

хвилеве трасування друкованих плат;

пошук компонент зв'язності в графі;

пошук найкоротшого шляху між двома вузлами незваженого графа;

пошук в просторі станів: знаходження рішення задачі з найменшим числом ходів, якщо кожен стан системи можна представити вершиною графа, а переходи з одного стану в інше - ребрами графа;

знаходження найкоротшого циклу в орієнтованому незваженому графові;

знаходження усіх вершин і ребер, що лежать на якому-небудь найкоротшому шляху між двома вершинами a і b;

пошук збільшуючого шляху в алгоритмі Форда-Фалкерсона (алгоритм Едмондса-Карпа).

Нехай заданий граф G = (V, Е) і виділена початкова (source) вершина s. Алгоритм пошуку завширшки систематично обходить усі ребра G для "відкриття" усіх вершин, досяжних з s, обчислюючи при цьому відстань (мінімальну кількість ребер) від s до кожної досяжної з s вершини. Крім того, в процесі обходу будується "дерево пошуку завширшки" з коренем s, що містить усі досяжні вершини. Для кожної досяжної з s вершини v шлях в дереві пошуку завширшки відповідає найкоротшому (тобто що містить найменшу кількість ребер) шляху від s до v в G. Алгоритм працює як для орієнтованих, так і для неорієнтованих графів.

Пошук завширшки має таку назву тому, що в процесі обходу ми йдемо вшир, тобто перш ніж приступити до пошуку вершин на відстані k +1, виконується обхід усіх вершин на відстані k.

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

Пошук завширшки будує дерево пошуку завширшки, яке спочатку складається з одного кореня, яким є початкова вершина s. Якщо в процесі сканування списку суміжності вже відкритої вершини і відкривається біла вершина v, то вершина v і ребро (u, v) додаються в дерево. Ми говоримо, що і є попередником (predecessor), або батьком (parent), v в дереві пошуку вшир. Оскільки вершина може бути відкрита не більше одного разу, вона має не більш одного батька. Взаємини предків і нащадків визначаються в дереві пошуку завширшки як завжди - якщо і знаходиться на шляху від кореня s до вершини v, то u є предком v, a v - нащадком u.

Приведена нижче процедура пошуку завширшки BFS припускає, що вхідний граф G = (V, Е) представлений за допомогою списків суміжності. Крім того, підтримуються додаткові структури даних в кожній вершині графа. Колір кожної вершини u і v зберігається в змінній color [u], а попередник - в змінній ? [u]. Якщо попередника у і немає (наприклад, якщо u = s або u не відкрита), то ? [u]= NIL. Відстань від s до вершини u, що обчислюється алгоритмом, зберігається в полі d[u]. Алгоритм використовує чергу Q типу FIFO для роботи з множиною сірих вершин

Взагалі черга в програмуванні це динамічна структура даних, що працює за принципом "перший прийшов - перший пішов" (англ. FIFO - first in, first out). У черги є голова (англ. head) та хвіст (англ. tail). Елемент, що додається до черги, опиняється в її хвості. Елемент, що видаляється з черги, знаходиться в її голові. Така черга повністю аналогічна звичній "базарній" черзі, в якій хто перший встав в неї, той першим буде обслуженим (але, на відміну від реальної черги, імовірність пройти поза чергою виключена)

Основні операції з чергою:

<#"justify">

Процедура BFS працює таким чином. У рядках 1-4 усіх вершини, за винятком початкової вершини s, забарвлюються в білий колір, для кожної вершини u полю d [u] привласнюється значення ?, а як батько для кожної вершини встановлюється nil. У рядку 5 початкова вершина s забарвлюється в сірий колір, оскільки вона розглядається як відкрита на початку процедури. У рядку 6 її полю привласнюється значення 0, а в рядку 7 її батьком стає nil. У рядках 8-9 створюється порожня черга Q, в яку поміщається один елемент s.

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

Легко побачити, що він виконується перед першою ітерацією і що кожна ітерація циклу зберігає інваріант. Перед першою ітерацією єдиною сірою вершиною і єдиною вершиною в черзі Q, являється початкова вершина s. У рядку 11 визначається сіра вершина u в голові черги Q, яка потім віддаляється з черги. Цикл for в рядках 12-17 переглядає усі вершини v в списку суміжності u. Якщо вершина v біла, значить, вона ще не відкрита, і алгоритм відкриває її, виконуючи рядки 14-17. Вершині призначається сірий колір, дистанція d [v] встановлюється рівною d[u] + 1, а як її батько вказується вершина u. Після цього вершина поміщається в хвіст черги Q. Після того, як усі вершини із списку суміжності u проглянуті, вершині u привласнюється чорний колір. Інваріант циклу зберігається, оскільки усі вершини, які забарвлюються в сірий колір (рядок 14), вносяться до черги (рядок 17), а вершина, яка віддаляється з черги (рядок 11), забарвлюється в чорний колір (рядок 18).

Результат пошуку завширшки може залежати від порядку перегляду вершин, суміжних з цією вершиною, в рядку 12. Дерево пошуку завширшки може змінюватись, але відстані d, вичислені алгоритмом, не залежать від порядку перегляду.

Оцінимо час роботи алгоритму для вхідного графа G = (V, E). Після ініціалізації жодна вершина не забарвлюється в білий колір, тому перевірка в рядку 13 гарантує, що кожна вершина вноситься до черги не більше одного разу, а отже, і віддаляється з черги вона не більше одного разу. Операції внесення до черги і видалень з неї вимагають O(1) часу, так що загальний час операцій з чергою складає О(V). Оскільки кожен список суміжності сканується тільки при видаленні відповідної вершини з черги, кожен список сканується не більше одного разу. Оскільки сума довжин усіх списків суміжності рівна ? (Е), загальний час, необхідний для сканування списків, рівний О(Е). Накладні витрати на ініціалізацію рівні О (V), так що загальний час роботи процедури BFS складає Про (V + Е). Таким чином, час пошуку завширшки лінійно залежить від розміру представлення графа G з використанням списків суміжності.

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

.2 Пошук в глибину

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

Як і у разі пошуку завширшки, коли вершина V відкривається в процесі сканування списку суміжності вже відкритої вершини u, процедура пошуку записує цю подію, встановлюючи поле попередника v ?[v] рівним u. На відміну від пошуку завширшки, де підграф передування утворює дерево, при пошуку в глибину підграф передування може складатися з декількох дерев, оскільки пошук може виконуватися з декількох початкових вершин.

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

Пошук в глибину також проставляє у вершинах мітки часу (timestamp). Кожна вершина має дві такі мітки - першу d [v], у якій вказується, коли вершина v відкривається (і зафарбовується в сірий колір), і друга - f[v], яка фіксує момент, коли пошук завершує сканування списку суміжності вершини v і вона стає чорною. Ці мітки використовуються багатьма алгоритмами і корисні при розгляді поведінки пошуку в глибину.

Приведена нижче процедура DFS записує в полі d [u момент, коли вершина u відкривається, а в полі f [u] - момент завершення роботи з вершиною u. Ці мітки часу є цілими числами в діапазоні від 1 до 2 |V|, оскільки для кожної з |V| вершин є тільки одна подія відкриття і одне - завершення. Для кожної вершини u виконується співвідношення:

До моменту часу d [u] вершина має колір WHITE, між d[u] і f[u] - колір GRAY, а потім f [u] - колір BLACK.

Далі представлений псевдокод алгоритму пошуку в глибину. Вхідний граф G може бути як орієнтованим, так і неорієнтованим. Змінна time - глобальна і використовується нами для міток часу.

Процедура DFS працює таким чином. У рядках 1-3 усіх вершини забарвлюються в білий колір, а їх поля ? ініціалізувалися значенням nil. У рядку 4 виконується скидання глобального лічильника часу. У рядках 5-7 по черзі перевіряються усі вершини з V, і коли виявляється біла вершина, вона оброблюється за допомогою процедури DFS_VISIT. Кожного разу при виклику процедури DFS_Visit(u) в рядку 7, вершина u стає коренем нового дерева лісу пошуку в глибину. При поверненні з процедури DFS кожній вершині u зіставляються два моменти часу - час відкриття (discovery time) d [u] і час завершення (finishing time) f[u].

При кожному виклику DFS_visit(u) вершина u спочатку має білий колір. У рядку 1 вона забарвлюється в сірий колір, в рядку 2 збільшується глобальна змінна time, а в рядку 3 виконується запис нового значення змінній time в полі часу відкриття d[u]. У рядках 4-7 досліджуються усі вершини, суміжні з u, і виконується рекурсивне відвідування білих вершин. При розгляданні в рядку 4 вершини v, суміжною з u, ми говоримо, що ребро (u, v) досліджується (explored) пошуком в глибину. І нарешті, після того, як будуть досліджені усі ребра, що покидають u, в рядках 8-9 вершина і забарвлюється в чорний колір, а в полі f [u] записується час завершення роботи з нею.

Зауважимо, що результат пошуку в глибину може залежати від порядку, в якому виконується розгляд вершин в рядку 5 процедур DFS, а також від порядку відвідування суміжних вершин в рядку 4 процедури DFS_visit. На практиці це зазвичай не викликає яких-небудь проблем, оскільки зазвичай ефективно використаний може бути будь-який результат пошуку в глибину, призводячи по суті до однакових результатів роботи алгоритму, що спирається на пошук в глибину.

Чому дорівнює час роботи процедури DFS? Цикли в рядках 1-3 і 5-7 процедури DFS виконуються за час ?(V), виключаючи час, необхідний для виклику процедури DFS_visit. Процедура DFS_visit викликається рівно по одному разу для кожної вершини, оскільки вона викликається тільки для білих вершин, і перше, що вона робить, - це забарвлює передану як параметр вершину в сірий колір. В процесі виконання DFS_Visit(v) цикл в рядках 4-7 виконується раз. Оскільки , загальна вартість виконання рядків 4-7 процедур DFS_VlSlT рівна ?(Е). Час роботи процедури DFS, таким чином, рівний ?(V + Е).

.3 Побудова мінімального остового дерева. Алгоритм Прима

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

Опишемо процедуру виконання цього алгоритму. Позначимо через N={1,2,…,n}множина вузлів мережі і введемо нові позначення:- множина вузлів мережі, з'єднаних алгоритмом після виконання k-й ітерації цього алгоритму,

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

Крок 0. Думаємо C0 = і = N.

Крок1. Вибираємо будь-який вузол і з множини визначаємо C1 = {i}, тоді = N-{i}. Думаємо k = 2.

Основний крок k. У множини вибираємо вузол j*, що з'єднаний самою короткою дугою з яким-небудь вузлом з множини Ck-1. Вузол j* приєднується до множини Ck-1 і видаляється з множини . Таким чином, Ck = Ck-1 + {j*}, = - {j*}.

Якщо множина порожня, то виконання алгоритму закінчується. У противному випадку думаємо k = k + 1 і повторюємо останній крок.

.4 Алгоритм Дейкстри

Алгоритм Дейкстры вирішує задачу про найкоротший шлях з однієї вершини в зваженому орієнтованому графові G = (V, Е) у тому випадку, коли ваги ребер не негативні.

Існують дві реалізації алгоритму: для пошуку найкоротшого шляху між двома парами вершин і від однієї вершини до усіх інших. Розглянемо реалізацію першого алгоритму на основі списку суміжних вершин

Особливості програмної реалізації:

·Нумерація вершин - цілі числа, починаючи з 0

·Список вершин виду реалізовується у вигляді двовимірної матриці з 3 стовпців. Кожен рядок матриці описує вершину. У 0 стовпці збережений статус вершини (тимчасова/постійна/перевірена постійна). У 1 стовпці зберігаємо компоненту відстані. У 2-му стовпці - номер попередньої вершини.

·Нескінченність представляємо як дуже велике число (на порядок більше суми усіх ребер графа)

Терміни:

Тимчасова вершина (0): вершина графа, до якої вже відомий який-небудь шлях

Постійна вершина (1): вершина графа, до якої вже відомий мінімальний шлях

Перевірена постійна вершина (2) : вершина графа, до якої вже відомий мінімальний шлях і прораховані усі шляхи до суміжних вершин

Початкові установки:

Кожній вершині графа ставимо у відповідність впорядковану пару . Перша координата пари : відстань від початкової вершини до поточної вершини. Друга координата пари : попередній вузол в дорозі від початку до цієї вершини.

Алгоритм.

) Починаємо у вузлі . В списку вершин привласнюємо їй значення (0, 0) і робимо її постійною.

) Основний крок. Для останньої вершини , визначеної як постійну, оцінюємо відстані з початку шляху через постійну вершину k до усіх суміжних вершин. Для цього знаходимо суму m і ваги ребра t з вершини vk до суміжної вершини vs і порівнюємо з наявним значенням в списку вершин. Якщо отриманий шлях менший за наявний, привласнюємо вершині vs значення (m+t, k). Статус вершини vs встановлюємо як тимчасова вершина.

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

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

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

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

.5 Модель Флойда-Уоршалла

Розглянемо завдання про пошук найкоротших шляхів між усіма парами вершин в орієнтованому графові G = (V, Е). Час роботи отриманого в результаті алгоритму, відомого як алгоритм Флойда-Уоршалла (Floyd - Warshall algorithm), рівно ?(V3). Наявність ребер з негативною вагою допускається, але передбачається, що цикли з негативною вагою відсутні.

У цьому алгоритмі мережа представлена у вигляді квадратної матриці з n рядками і n стовпцями. Елемент (i,j) дорівнює відстані dij від вузла i до вузла j, що має кінцеве значення, якщо існує дуга (i,j), і дорівнює нескінченності в противному випадку.

Покажемо спочатку основну ідею методу Флойда-Уоршалла. Нехай є три вузли i,j і k і задані відстані між ними (рисунок 2.1). Якщо виконується нерівність dij+djk<dik, то доцільно замінити шлях i ® k шляхом i ® j ® k. Така заміна (далі її будемо умовно називати трикутним оператором) виконується автоматично в процесі виконання алгоритму Флойда.

Рисунок 2.1 - Трикутний оператор

Алгоритм Флойда-Уоршалла вимагає виконання наступних дій.

Крок 0. Визначаємо початкову матрицю відстаней D0 і матрицю послідовності вузлів S0. Діагональні елементи обох матриць позначаються знаком ''- '', що показує, що ці елементи в обчисленнях не беруть участь. Думаємо k = 1.

Основний крок k. Задаємо рядок k і стовпець k як ведучий рядок і ведучий стовпець. Розглядаємо можливість застосування трикутного оператора до всіх елементів dij матриці Dk-1. Якщо виконується нерівність dik+dkj<dij, (i?k,j¹k і i¹j), тоді виконуємо наступні дії:) створюємо матрицю Dk шляхом заміни в матриці Dk-1 елемента dij на суму dik+dkj,

б) створюємо матрицю Sk шляхом заміни в матриці Sk-1 елемента sij на k. Думаємо k=k+1 і повторюємо крок k.

Після реалізації n кроків алгоритму визначення по матрицях Dn і Sn найкоротшого шляху між вузлами i і j виконується за наступними правилами.

. Відстань між вузлами i і j дорівнює елементові dij у матриці Dn.

. Проміжні вузли шляху від вузла i до вузла j визначаємо по матриці Sn. Нехай sij=k, тоді маємо шлях i-k-j. Якщо далі sik=k і skj=j, тоді вважаємо, що весь шлях визначений, тому що знайдені всі проміжні вузли. У противному випадку повторюємо описану процедуру для шляхів від вузла i до вузла k і від вузла k до вузла j.

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

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

3. Програмна реалізація алгоритмів

.1 Огляд можливостей мови програмування

Середовище виконання (runtime) було завжди присутнє в Visual Basic, тому наступне твердження спочатку виглядає декілька дивно. Отже, одним з найсерйозніших нововведень VB.NET являється наявність середовища виконання CLR (Common Language Runtime), загального для усіх мов .NET. Хоча на перший погляд CLR нагадує звичайну бібліотеку часу виконання на кшталт бібліотеки С MSVCRTXX.DLL, бібліотека VB MSVBVMXX.DLL має значно великі розміри і має набагато більші можливості. З цієї причини написання програм, повною мірою використовуючих CLR, більше схожий на програмування для API нової операційної системи Проте, можливості бібліотеки класів .NET Framework настільки широкі, що вам практично не доведеться використовувати функції API.

Оскільки усі мови .NET використовують одне і те ж середовище CLR, необхідність в середовищах виконання для окремих мов відпадає. Більше того, код, призначений для виконання в CLR, може бути написаний на будь-якій мові і з однаковим успіхом використовуватися в усіх мовах, відповідних специфікації CLR. В цьому проявляться головна відмінність .NET від Java: на платформі .NET можна використовувати будь-яку мову за умови, що він відповідає специфікації CLR. Програма, написана на Java, працює на будь-якій платформі (принаймні теоретично - на практиці виникають проблеми), але за умови, що вона написана саме на Java. Ймовірно, саме мовна інтеграція стане однією із складових успіху .NET. Зокрема, код VB може використовуватися в програмах, написаних на С#, і навпаки, причому це не зажадає додаткових зусиль з боку програміста.

Наступне принципове нововведення - загальний формат виконуваного коду .NET, так званий Microsoft Intermediate Language (проміжна мова Microsoft), MSIL або просто IL Він є кодом, що частково відкомпілювався, перетворюється в машинний код середовищем .NET під час виконання. Перед нами принципове удосконалення схеми, що існувала в усіх версіях VB до версії 5. Раніше додатка VB компілювалися в Р-код (псевдокод, машинна мова абстрактної машини), свого роду проміжне представлення остаточного виконуваного коду.

Механізм часу виконання інтерпретував Р-код при запуску програми користувачем. Користувачі постійно скаржилися на погану швидкодію і прохали Microsoft включити в VB підтримку компіляції в машинний код. Починаючи з версії 5 з'явилася можливість вибору між компактним Р-кодом і машинним (native) кодом, який займав більше місця, але теоретично швидше працював.

У мовах .NET переваги Р-коду об'єдналися з перевагами компільованих мов. Спочатку програма, написана на будь-якій мові, компілюється в IL (віддалений аналог Р-коду), а потім отриманий IL -код перетвориться в машинний код. Подібна двокрокова схема відносно легко забезпечує міжмовну сумісність, а підсумкове використання машинного коду забезпечує хорошу швидкодію.

Об'єктно-орієнтовані засоби VB5 і VB6 були, м'яко кажучи, обмеженими. Зокрема, ці версії VB не дозволяли автоматично ініціалізувати дані класу при створенні екземпляра. В результаті об'єкт створювався в невизначеному стані, що підвищувало вірогідність помилок і примушувало програміста приймати додаткові заходи обережності при роботі з об'єктами. Для вирішення цієї проблеми в VB.NET з'явилися конструктори, що параметризувалися.

Іншим недоліком була відсутність повноцінного спадкоємства. Спадкоємством називається особлива форма багатократного використання кода, при якій програміст визначає нові об'єкти на базі існуючих об'єктів. Спадкоємство дуже добре підходить для таких завдань, як створення нового текстового поля з розширеними можливостями на підставі стандартного текстового поля. У VB версій 5 і 6 спадкоємство не підтримувалося, тому для побудови поліпшеного текстового поля доводилося удаватися до послуг незручної і ненадійної програми-майстри (wizard).

Розглянемо інший приклад, в якому було б доречне спадкоємство, - створення класів для роботи із спеціалізованими колекціями. Щоб створити колекцію, що спеціалізувалася на зберіганні строкових даних, в VB5 і 6 в клас включалося закрите поле:mCollection As Collection

У обробниках подій Initialize і Terminate відбувалося виділення і звільнення пам'яті, використовуваною закритою колекцією. Потім програмувалися методи спеціалізованої колекції, призначені для зовнішнього використання. Більшість таких методів зводилися до простого виклику відповідного методу закритої колекції, наприклад:Add(Item As String).Add ItemSub

Але найосоружніше починалося у тому випадку, якщо вміст колекції вимагалося перебирати в циклі For Each. Для цього в модуль класу доводилося включати фрагменти виду:Function NewEnum As lUnknownNewEnum = mCollection.[_NewEnum]Function

Але і це не усе - цій функції слід було присвоїти ідентифікатор! Принцип "абракадабра - дістаємо з капелюха кролика"! хороший для фокусника, але не для програміста. При використанні спадкоємства уся ця нісенітниця не потрібна. У VB.NET досить написати:MyCollectionCollection

...і ви отримуєте автоматичну підтримку For Each.

У програмістів, що працюють на Visual Basic, завжди виникали проблеми з витоком пам'яті із-за так званих циклічних посилань (ситуація, при якій об'єкт А посилається на об'єкт В, а об'єкт В посилається на об'єкт А). Якщо поява циклічних посилань була обумовлена логікою програми, компілятор VB не розпізнавав їх, внаслідок чого пам'ять, займана цими об'єктами, не звільнялася.

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

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

Простір імен System.Collections бібліотеки .NET Framework містить інтерфейси і класи, які визначають різні колекції об'єктів, такі як списки, черги, двійкові масиви, хэш-таблицы і словники. Колекції настільки важливі, що вони за умовчанням автоматично імпортуються в кожне рішення VB .NET.

В сукупності ці класи залишають далеко позаду примітивний клас Collection з VB6. Найкорисніші класи колекцій перераховані в таблиці 3.1.

Детальніше розглянемо основні принципи роботи з двома найважливішими класами: ArrayList і HashTable.

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

Таблиця 3.1 - Основні класси коллекций

Імя класуОписArrayListДинамічний масив, розміри якого збільшуються і зменшуються у міру потребиBitArrayВикористовується для порозрядних операцій з окремими бітамиHashtableКолекція пар "ключ/значення", впорядкована за хеш-кодам ключівQueueЧерга (принцип FIFO, "першим прийшов, першим вийшов")StackСтік (принцип LIFO, "останнім прийшов, першим вийшов")DictionaryBaseБазовий клас для різних асоціативних масивів (словників). У асоціативному масиві зберігаються пари "ключ/значення", і працювати з ними зручніше, ніж з багатьма типами колекцій.

Використання ArrayList замість базового масиву означає, що вам не доведеться часто викликати ReDim Preserve для збереження існуючих даних. Досить викликати метод Add, і клас ArrayList сам виконає усю чорнову роботу. Клас ArrayList містить ряд інших корисних методів. Наприклад, метод AddRange дозволяє перенести в динамічний масив увесь вміст існуючого масиву всього однією командою. Після завершення обробки елементи можна скопіювати назад. Зокрема, це дозволяє легко об'єднати вміст двох масивів. У таблиці 3.2 перераховані основні члени класу ArrayList.

Таблиця 3.2 - Найважливіші члени класу ArrayList

Ім'яОписCopy ToКопіює об'єкт ArrayList (повністю або частково) в одновимірний масив починаючи із заданого індексу масиву-приймачаContainsПеревіряє, чи присутній в об'єкті ArrayList заданий елементClearВидаляє усі елементи з об'єкту ArrayListCapacityОтримує або задає максимальну кількість елементів, на яку розрахований об'єкт ArrayList. Звичайно, місткість масиву змінюється у міру додавання нових елементів, але з міркувань ефективності місткість нарощується великими "порціями"BinarySearchВиконує бінарний пошук заданого елементу у відсортованому динамічному масиві або в його частиніAddRangeДозволяє додати вміст іншого масиву (динамічного або звичайного) в поточний динамічний масив. У поєднанні з методом InsertRange дозволяє швидко об'єднувати масиви з використанням Arraylist як допоміжний класAddДодає новий об'єкт в кінець динамічного масивуCountПовертає кількість елементів, що фактично зберігаються в масивіGetRangeПовертає інший об'єкт ArrayList, що містить послідовність суміжних елементів поточного об'єктуIndexOfПовертає індекс першого входження заданого елементу в динамічний масив. Слід пам'ятати, що індексація в класі ArrayList (як і в звичайних масивах) починається з нуляInsertВставляє елемент в задану позицію об'єкту ArrayListInsertRangeВставляє елементи колекції в об'єкт ArrayList починаючи із заданої позиціїItemОтримує або задає значення елементу, що знаходиться в заданій позиції. Є властивістю за умовчанням для класу ArrayListLastlndexOfПовертає індекс останнього входження заданого елементу в динамічний масив (індексація починається з нуля)LengthПовертає кількість елементів в динамічному масивіReadonlyПовертає новий об'єкт ArrayList, доступний тільки для читання

Серед властивостей класу ArrayList найбільший інтерес представляє властивість Item, яка представляє елемент із заданим індексом. Властивість Item є властивістю за умовчанням класу ArrayList. Це означає, що при використанні його ім'я може не вказуватися

Прості і динамічні масиви зручні передусім тим, що ви можете безпосередньо звернутися до будь-якого елементу по індексу. Звичайно, для цього необхідно знати індекс. У наступній структурі даних - хеш-таблиці - довільний доступ до даних здійснюється по ключу. Допустимо, у вас є хэш-таблица з ім'ям theData. Команда theData("some keys") дозволяє витягнути з хеш-таблиці потрібний елемент без циклічного перебору усього вмісту. Хеш-таблиці дуже зручні в ситуаціях, коли ви хочете дістати швидкий доступ до значення по пов'язаному з ним унікальному атрибуту, тобто ключу. Зрозуміло, програмування хеш-таблиці - завдання непросте. Для цього необхідно побудувати хорошу функцію хешування для обчислення індексу даних по ключу, а також розв'язати неминучу проблему колізій, тобто збіги хеш-кодов у двох різних елементів, але, на щастя, ця робота вже виконана за вас розробниками .NET Framework.

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

У таблиці 3.3 перераховані найважливіші методи класу Hashtable. Методи класу HashTable враховують регістр символів в строкових ключах.

Таблица 3.3 - Найважливіші методи класу Hashtable

Ім'яОписAddДодає нову пару "ключ/значення" в хэш-таблицуClearВидаляє з хеш-таблиці увесь вмістContainsKeyПеревіряє, чи містить хеш-таблиця заданий ключ (з урахуванням регістра символів)ContainsValueПеревіряє, чи містить хеш-таблиця задане значення (з урахуванням регістра символів)СоруТоКопіює елементи хеш-таблиці в масивCountПовертає кількість пар "ключ/значення" в хеш-таблиціItemВластивість за умовчанням. Отримує або задає значення, пов'язане з вказаним ключемKeysПовертає усі ключі хеш-таблиці у вигляді колекції, вміст якої перебирається в циклі For - EachRemoveВидаляє з хеш-таблиці значення із заданим ключемValuesПовертає усі значення хеш-таблиці у вигляді колекції, вміст якої перебирається в циклі For - Each

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

Для відображення побудованого графу не обійтися без графічного програмування. Графічне програмування в .NET Framework повністю відрізняється від усього, що було реалізовано в колишніх версіях VB. Знайомі графічні команди (частково запозичені ще з QuickBasic) зникли. З числа принципових змін також слід звернути увагу на відсутність властивості AutoRedraw або його аналогів. У колишніх версіях VB властивість AutoRedraw, рівне True, позбавляла програміста від необхідності програмувати процедуру події Paint для того, щоб забезпечити відновлення графічного зображення в елементі.

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

У програмістів з досвідом роботи в GDI перехід на GDI+ часто викликає шок, оскільки графічний вивід в .NET відбувається без збереження стану. Інакше кажучи, кожна графічна команда повинна містити повну інформацію про виконувану операцію. Скажімо, якщо ви використовували чорну кисть в першому рядку програми і хочете знову скористатися нею в другому рядку, необхідно вказати графічній системі, що операція повинна виконуватися чорною кистю. GDI+ "не пам'ятає" про операції, що виконувалися раніше.

Класи GDI+ знаходяться в просторах імен System.Drawing, System.Drawing. Drawing2D, System.Drawing.Imaging і System.Drawing.Text. Ці простори імен входять в зборку System.Drawing, посилання на яку створюється автоматично при виборі типу додатка Windows Application в діалоговому вікні New Project.

Велика частина графічного виводу в GDI+ здійснюється перевизначенням процедури. Це не подія, хоча кінець кінцем перемальовування і призводить до виклику події OnPaint базового класу форми або елементу. Процедура OnPaint грає таку ж важливу роль, як і в колишніх версіях VB : вона забезпечує відновлення зображення при тимчасовому прихованні або згортанні форми. Сигнатура цієї важливої процедури виглядає таким чином: Protected Overrides Sub OnPaint(ByVal e As PaintEventArgs)

Виведення здійснюється на графічній поверхні GDI+, представленій екземпляром класу Graphics. Процедура OnPaint класу Form інкапсулює таку поверхню у вигляді значення властивості e.Graphics.

Хоча будь-яка форма або елемент (у тому числі і PictureBox) з підтримкою виводу дозволяє дістати доступ до свого графічного вмісту за допомогою виклику ControlName.CreateGraphics, будьте дуже уважні, якщо це відбувається за межами процедури Paint. Між виводом в графічному контексті, отриманим викликом e.Graphics в процедурі OnPaint і написанням коду, використовуючого CreateGraphics, існують тонкі відмінності.

Розглянемо основні методи для малювання ліній, прямокутників і інших фігур. Перед операціями такого роду слід отримати об'єкт пера, який є екземпляром класу System.Drawing.Pen. Найпоширеніший конструктор класу Ріпи має наступний синтаксис:Sub New(Color, Single)

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

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

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

Еліпси малюються методом DrawEllipse. Навколо кожного еліпса можна описати прямокутник. Якщо ви хочете накреслити еліпс, уявите прямокутник, описаний навколо нього, і параметрами для методу DrawEllipse вкажіть параметри для малювання цього уявного прямокутника. Круг - це еліпс, у якого однакові ширина і висота, тому креслиться тим же методом.

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

Аналогічно тому, як для малювання ліній фігур ви повинні вибрати перо, для малювання зафарбованих фігур ви повинні вибрати кисть. Подібно до того, як існує клас Pens, що містить декілька десятків пір'я різних кольорів, існує і спеціальний клас Brushes, що містить декілька десятків кистей різних кольорів. Запис Brushes.Blue означає узяту кисть синього кольору.

Звернення до методів малювання зафарбованих фігур відрізняється від звернення до методів малювання таких же незафарбованих фігур тільки тим, що в дужках ви замість пера вказуєте кисть, а метод називається не Draw а Fill. Зафарбований прямокутник малюється методом FillRectangle, а зафарбований еліпс малюється методом FillEllipse.

Метод DrawString об'єкту Graphics призначений для виведення тексту. При виклику цього методу задається об'єкт шрифту, колір, кисть і початкова точка виводу. У GDI+ повністю підтримується кодування Unicode, що дозволяє виводити текст на будь-якій мові.

.2 Опис функцій програмної моделі

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

Структури:

GraphVertex: структура для зберігання даних, необхідних для відображення вершини графу;

GraphRib: структура для зберігання даних, необхідних для відображення ребра графу;

NextTop: структура для зберігання інформації про суміжну вершину у випадку представлення графу як списку суміжних вершин.

Загальнодоступні змінні:

SizeHeight типу Integer: розмір вершини графу при її відображенні;

nextIDHeight типу Integer: містить індекс наступної вершини при її додаванні;

nextIDRib типу Integer: містить індекс наступного ребра при його додаванні;

arrVertex типу Hashtable: колекція вершин графу для зображення на формі;

arrRib типу ArrayList: колекція ребер графу для зображення на формі;

arrMarkRib типу ArrayList: колекція індексів ребер графу, які необхідно виділити при зображенні на формі.

Процедури-методи:

DrawGraph: призначений для відображення графу на формі;

DFS_Visit: реалізує основний крок алгоритму пошуку в глибину;

PrintPath: після виконання алгоритмів пошуку в глибину або в ширину виводить шлях між заданими вершинами графу;

PrintVector: друкує отриманий одновимірний масив на формі;

MarkRib: помічає ребро, що зєднує передані вершини;

PrintMatrix: друкує отриманий двовимірний масив на формі.

Процедури-функції:

CreateList() As ArrayList(): повертає представлення побудованого графу у вигляді списків суміжності;

CreateMatrix(Optional ByVal MaxVal As Integer = 0) As Integer(,):повертає представлення побудованого графу у вигляді матриці суміжності. При необхідності, відсутні ребра заповнюються отриманим значенням MaxVal;

IntBox(ByVal promt As String, Optional ByVal Val As Integer = 0, Optional ByVal minVal As Integer = 0, Optional ByVal maxVal As Integer = 0) As Integer: організує введення цілого числа у заданому інтервалі;

CopyMatrix(ByVal a(,) As Integer) As Integer(,): повертає копію отриманої матриці.

Процедури обробки подій:

PictureBox1_Click: відбувається при натисненні на графічному полі. Додає у вказаній точці нову вершину графу;

btnAddRid_Click: відбувається при натисненні по кнопці «Додати». Додає ребро до графу;

btnDFC_Click: відбувається при клацанні на кнопці «Пошук в глибину (DFC)». Для побудованого графу запускає виконання вищезгаданого алгоритму;

btnBFC_Click: відбувається при клацанні на кнопці «Пошук в ширину (BFC)». Для побудованого графу запускає виконання вищезгаданого алгоритму;

btnPrim_Click: відбувається при клацанні на кнопці «Остове дерево (Алгоритм Прима)». Для побудованого графу запускає виконання вищезгаданого алгоритму;

btnDeicstra_Click: відбувається при клацанні на кнопці «Найкоротший шлях між 2 вершинами (Дейкстра)». Для побудованого графу запускає виконання вищезгаданого алгоритму;

btnFloid_Click: відбувається при клацанні на кнопці «Найкоротший шлях між усіма вершинами (Флойд)». Для побудованого графу запускає виконання вищезгаданого алгоритму;

btnSaveToFile_Click: відбувається при клацанні на кнопці «Зберігти граф в файл». Виконує зберігання побудованого графу у зовнішній файл.

btnReadFromFile_Click: відбувається при клацанні на кнопці «Зчитати граф з файлу». Виконує побудову збереженого графу з зовнішнього файлу.

Всі процедури та функції оголошені як закриті (Private)

3.3 Інтерфейс програми

Головне вікно програми наведено на рисунку 3.1

Рисунок 3.1 - Головне вікно програми

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

Рисунок 3.2 - Головне вікно програми після побудови графу

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

Для прикладу виконаємо алгоритм побудови остового дерева (алгоритм Прима). Результат роботи наведено на рисунку 3.3.

Рисунок 3.3 - Головне вікно програми після виконання алгоритму Прима

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

Файл з графом з технічної точки зору є текстовим файлом з розширенням *.grf та мае певну структуру. Для побудованого вище графу вміст файлу наведено на рисунку 3.4

Рисунок 3.4 - Приклад файлу, що зберігає побудований граф

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

перше число: індекс вершини графа;

друге та третє числа: координати X та Y для зображення вершини на площині;

трете число: кількість суміжних вершин;

останні числа: пари чисел вигляду <індекс суміжної вершини> <вага ребра>, кількість пар відповідає кількості суміжних вершин.

Усі числа в рядках відділені один від одного одним пробілом.

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

ВИСНОВКИ

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

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

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

В якості подальшого розвитку системи можна запропонувати візуалізацію роботи алгоритмів для підвищення дидактичної цінності розробленої програми. Результати роботи можуть бути використані під час викладання курсу «Дискретна математика».

ПЕРЕЛІК ВИКОРИСТАНИХ ДЖЕРЕЛ

1.Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клиффорд. Алгоритмы: Построение и анализ, 2-е издание.: Пер. с англ. - М.: ИД «Вильямс», 2005. - 1296 с.

.Берж К. Теорія графів і її застосування. - М.: МУЛ, 1962.

.Зиков А. А. Теорія кінцевих графів. - Новосибірськ: Наука, 1969.

.Касаткін В. Н. Незвичайні задачі математики. - К.: Радянська школа, 1987.

.Оре О. Графи і їх застосування. - М.: Світ, 1965.

.Реньє А. Трилогія про математика. - М.: Світ , 1980.

.Роббинс Джон. Отладка приложений для Microsoft.NET и Microsoft Windows - М. Русская Редакция, 2004. - 736 с.

.Нортрап Тони, Вилдермьюс Шон, Райан Билл. Основы разработки приложений на платформе Microsoft.NET Framework - Питер, Русская Редакция, 2007. - 864 с.

.Кристиан Гросс. C# 2008 и платформа.NET 3.5 Framework: от новичка до профессионала, 2-е издание - Вильямс, 2009. - 897 с.

.Джимми Нильссон. Применение DDD и шаблонов проектирования: проблемно-ориентированное проектирование приложений с примерами на C# и.NET - Вильямс, 2007. - 429 с.

.Дон Бокс, Крис Селлз. Основы платформы.NET, том 1. Обще языковая исполняющая среда. - Вильямс, 2003. - 288 с.

.Роберт Седжвик. Фундаметальные алгоритмы на С++. Часть 5. Алгоритмы на графах - ДиаСофтЮП, 2002. - 496 с.

.Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. Изд.2, испр. - 2009. 392 с.

.Харари Фрэнк. Теория графов - Едиториал УРСС, 2003. - 297 с.

.Кристофидес Н. Теория графов. Алгоритмический подход. Перевод на русский язык. - Наука, 1989. 241 с.

.Камерон П. Теория графов. Теория кодирования и блок-схемы. Перевод на русский язык. - Наука, 1980. 140 с.

.Акимов О.Е. Дискретная математика: логика, группы, графы, фракталы. - Едиториал УРСС, 2005. - 655 с.

.Харари Ф. Теория графов: Перевод с английского. - Едиториал УРСС, 2006. - 300 с.

.Скакунов Александр. Алгоритмы и структуры данных. - Едиториал УРСС, 1996. 357 с.

.Уоррен Генри С. Алгоритмические трюки для программистов. - Диалектика-Вильямс, 2003. - 288 с.

.Visual Studio .NET: разработка приложений баз данных. -СПб.: БХВ-Петербург, 2003. - 544 с.: ил.

.Visual Basic .Net: учебный курс / В.Долженков, М.Мозговой. - СПб.: Питер, 2003. - 264 с.

ЗМІСТ ВСТУП . Загальний огляд проблеми та обґрунтування вибору програмних засобів .1 Значення алгоритмів на графах .2 Визначення та способи пред

Больше работ по теме: