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

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

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

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

  1. Панель інструментів: містить дві кнопки типу TSpeedButton («Додати вершину»«Додати ребро») призначені для побудови графа і дві кнопки типу TButton («Видалити граф»«Знайти компоненти зв'язності»), одна з яких призначена для видалення побудованого графа і друга — реалізує процес побудови дерева обходу в глибину і з його допомогою визначає зв'язні вершини.
  2. Графічний редактор: призначений для побудови та візуалізації неорієнтованого графа. Опишемо, яким чином це реалізується. Отже, для того, щоб намалювати вершини графа потрібно, на першому кроці, активізувати кнопку панелі задач «Додати вершину». Далі, з допомогою лівої кнопки мишки розставити їх у відповідній області форми. Після того, як вершини створено потрібно пов'язати їх неорієнтованим ребром. Неорієнтоване ребро в даній програмі створюється аналогічним чином. Тобто активізувавши кнопоку «Додати ребро» лівою кнопокою миші поєднюємо відповідні вершини. Для видалення графа необхідно скористатися однойменною кнопкою.
  3. Область виводу результатів: панель типу TStatusBar, яка міститься в нижній частині форми, основним призначенням якої є вивід вершин, що входять в кожну компоненту зв'язності.

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

zvjaznist_grafa_poshuk_v_glybynu_delphi1

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

Отже, запустимо delphi-проект та з допомогою графічного редактора побудуємо вершини неорієнтованого графа.

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

Далі, поєдняємо їх відповідними неорієнтованими ребрами. В результаті виконання даного кроку, головна форма пректу набуде наступного вигляду:

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

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

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

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

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар