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

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

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

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

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

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

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

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

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.