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

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

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

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

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

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

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

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

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

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

Терміни:

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

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

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

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

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

Алгоритм.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

a) створюємо матрицю Dk шляхом заміни в матриці Dk-1 елемента dij на суму dik+dkj,

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

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

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

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

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

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

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

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 в клас включалося закрите поле:

Private mCollection As Collection

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

Sub Add(Item As String)

mCollection.Add Item

End Sub

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

Public Function NewEnum As lUnknown

Set NewEnum = mCollection.[_NewEnum]

End Function

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

Class MyCollection

Inherits Collection

...і ви отримуєте автоматичну підтримку 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	Видаляє усі елементи з об'єкту ArrayList
Capacity	Отримує або задає максимальну кількість елементів, на яку розрахований об'єкт ArrayList. Звичайно, місткість масиву змінюється у міру додавання нових елементів, але з міркувань ефективності місткість нарощується великими "порціями"
BinarySearch	Виконує бінарний пошук заданого елементу у відсортованому динамічному масиві або в його частині
AddRange	Дозволяє додати вміст іншого масиву (динамічного або звичайного) в поточний динамічний масив. У поєднанні з методом InsertRange дозволяє швидко об'єднувати масиви з використанням Arraylist як допоміжний клас
Add	Додає новий об'єкт в кінець динамічного масиву
Count	Повертає кількість елементів, що фактично зберігаються в масиві
GetRange	Повертає інший об'єкт ArrayList, що містить послідовність суміжних елементів поточного об'єкту
IndexOf	Повертає індекс першого входження заданого елементу в динамічний масив. Слід пам'ятати, що індексація в класі ArrayList (як і в звичайних масивах) починається з нуля
Insert	Вставляє елемент в задану позицію об'єкту ArrayList
InsertRange	Вставляє елементи колекції в об'єкт ArrayList починаючи із заданої позиції
Item	Отримує або задає значення елементу, що знаходиться в заданій позиції. Є властивістю за умовчанням для класу ArrayList
LastlndexOf	Повертає індекс останнього входження заданого елементу в динамічний масив (індексація починається з нуля)
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 - Each
Remove	Видаляє з хеш-таблиці значення із заданим ключем
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. Найпоширеніший конструктор класу Ріпи має наступний синтаксис:

Public Sub New(Color, Single)

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

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

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

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

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

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

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

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

3.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 с.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Размещено на Allbest.ru