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

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

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

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

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

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

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

Знаходження компонент сильної зв'язності орієнтованого графа

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

komponenty_sylnoi_zvjaznosti_grafa110

Орієнтований граф та його компоненти сильної зв'язності

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

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