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

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

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

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

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

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

Побудова орієнтованого графа

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

Вивід компонент сильної зв’язності заданого орієнтованого графа

Скачати delphi-проект Знаходження всіх компонент сильної зв’язності орієнтованого графа.

Залишити коментар

Your email address will not be published. Required fields are marked *

*