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

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

Відмітимо, що для розв'язку задач такого типу, зазвичай, використовують один з двох алгоритмів. Це обхід графа в глибину або обхід графа в ширину. Розглядуваний delphi-проект реалізує перший з них.

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

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

Перевірка неорієнтованого графа на зв'язність та ациклічність

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

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

Побудова мінімального кістятка за алгоритмом Борувки в середовищі програмування delphi

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

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

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

Побудова мінімального кістяка в неорієнтованому графі використовуючи алгоритм Борувки

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

Ілюстрація роботи алгоритму Борувки

Ілюстрація роботи алгоритму Борувки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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