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

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

Отже, після запуску програми, на екрані появиться форма наступного вигляду.

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

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

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

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

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

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

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

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

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

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