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

Delphi-програма, для заданого орієнтованого графа, виводить всі компоненти сильної зв'язності (нагадаємо, що компонентою сильної зв'язності орієнтованого графа, називається така підмножина його вершин, що будь-які дві вершини цієї підмножини, досяжні одна з одної). У програмі передбачено візуальне формування графа за допомогою миші. Для цього, на головній формі міститься графічний редактор (компонент типу TImage) та дві кнопки типу TSpeedButton («Додати вершину» і «Додати ребро»). Підготовка проекту до нового прикладу здійснюється з допомогою кнопки «Видалити граф» (компонент типу TButton). При натисканні на кнопку «Пошук компонент сильної зв'язності» (також компонент типу TButton) власне і запускається алгоритм пошуку сильно зв'язних компонент заданого графа. Результат виконання алгоритму відображається в області виводу результатів (компонент типу TStatusBar).

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

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

Орієнтований граф

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

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

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

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

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

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

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

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

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

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