Графічне представлення орієнтованого графа засобами Delphi

В параграфі Графічне представлення графа засобами Delphi ми створили проект, який малював неорієнтований граф на канві компонента Image1. Сьогодні розглянемо алгоритм побудови орієнтованого графа, тобто графа ребрам якого присвоєно певний напрямок. Послідовність дій при побудові вершин орієнтованого графа аналогічна послідовності дій, яку ми здійснювали у випадку неорієнтованого. Проте, процес побудови орієнтованого ребра дещо відрізняється. Для того, щоб нарисувати орієнтоване ребро, будемо використовувати наступний алгоритм: нехай маємо дві вершини графа (зображені у вигляді кола з центром у точках V1 та V2 і радіусом r). Для того, щоб побудувати ребро проведемо від точки V1 до V2 пряму лінію. Далі для того, щоб задати напрямок необхідно знайти точку перетину кола з центром в точці V2 та радіусом r з прямою, яка прорходить через дві точки V1 та V2. В результаті отримаємо деяку точку A. Далі, побудуємо деяке уявне коло з радіусом r1 (на малюнку зображено штрихпунктирною лінією), і знову знайдемо точку перетину даного кола з прямою V1V2. Отримуємо деяку точку B. Після того, як координати точки B відомі, виконуємо поворот даної точки відносно точки A, проти годинникової стрілки на кут l. В результаті отримуємо точку B1. Аналогічно, виконуємо поворот точки B за годинниковою стрілкою — отримуємо точку B2. Таким чином ми отримали трикутник AB1B2, який і буде вказувати напрямок орієнтованого ребра.

Читати повністю

Графічне представлення графа засобами Delphi

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

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

Читати повністю

Визначення найкоротшого шляху за алгоритмом Флойда

Основна ідея алгоритму Флойда полягає в наступному: нехай є три вершини графа i, j і k, які поєднані між собою ребрами заданої довжини.

Алгоритм Флойда

Трикутний оператор Флойда

Якщо виконується нерівність Алгоритм Флойда, то доцільно замінити маршрут від вершини i до  вершини k (Алгоритм Флойда) маршрутом Алгоритм Флойда. Така заміна (іншими словами трикутний оператор) виконується в процесі виконання алгоритму Флойда.

Алгоритм Флойда складається з n етапів (де n кількість вершин графа).

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

Читати повністю

Алгоритм Крускала

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

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

Алгоритм Крускала

Крок 1: вибираємо ребро найменшої вартості: 1−3=1. В результаті отримаємо одне дерево, яке складається з двох вершин і одного ребра (на малюнку позначено зеленим кольором) та 4 дерева, які містять по одній вершині.

Читати повністю

Знаходження дерева мінімальної вартості за алгоритмом Крускала на Delphi(2)

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

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

Алгоритм Крускала на Delphi

Читати повністю

Алгоритм Прима

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

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

algoritm_prima1

В якості початкової вибираємо будь-яку вершину графа, нехай вона буде під номером 1. Вершина №1 з'єднана з вершинами  №2, №3 і №4. Вибираємо серед них ту, яка має з вершиною 1 ребро найменшої довжини. В нашому прикладі такою є вершина 3 (довжина ребра рівна одиниці). Додаємо її до дерева.

Читати повністю

Знаходження дерева мінімальної вартості за алгоритмом Прима на Delphi(2)

Для запуску програми активуємо exe — файл «Project1.exe». В результаті відкриється форма наступного виду:

algoritm_prima_delphi21

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

Під панеллю інструментів форма ділиться на дві частини. Ліва частина («Граф») призначена для побудови графа, і права частина («Матриця суміжності»), яка містить відстані між вершинами.

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

Читати повністю

« Попередня сторінкаНаступна сторінка »