Перевірка неорієнтованого графа на наявність циклів в середовищі програмування delphi

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

Отже, delphi-проект складається з однієї форми, яка в свою чергу складається з наступних елементів: панель інструментів (компонент типу TPanel — служить контейнером для чотирьох кнопок «Додати вершину», «Додати ребро», «Видалити граф», «Перевірити граф на наявність циклів»), графічний редактор (компонент типу TImage) та область виводу результатів (компонент типу TMemo). Перші два з них призначені для побудови та графічного представлення неорієнтованого графа і третій — виводить, у вигляді послідовності вершин, в якій кожна вершина з'єднана з наступною ребром, всі цикли, які містить розглядуваний граф.

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

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

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

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

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

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

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

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

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

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

Побудова дерева обходу в ширину в середовищі програмування delphi

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

Після того, як з теорією розібралися, перейдемо до розгляду delphi-проекту. Отже, після запуску програми, на екрані появиться форма наступного вигляду.

Пошук в ширину на delphi

Головне вікно проекту "Побудова дерева обходу в ширину для неорієнтованого графа"

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

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

Побудова дерева обходу в глибину в середовищі програмування delphi

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

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

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

Знаходження найкоротшого шляху між двома вершинами в орієнтованому графі використовуючи алгоритм Дейкстри

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

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

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

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

Рішення задачі комівояжера методом найближчого сусіда в середовищі програмування delphi

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

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

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

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

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