Пошук мостів в неорієнтованому графі засобами delphi

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

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

Побудова дерева обходу в глибину в середовищі програмування delphi

Delphi-програма реалізує один з найвідоміших алгоритмів обходу графа, а саме пошук в глибину. Основна суть даного алгоритму полягає в наступному: рухатися вглиб, поки це можливо (є не пройдені ребра), і повертатися і шукати інший шлях, коли таких ребер немає. Відмітимо, що така процедура виконується до тих пір, поки всі вершини, досяжні з вихідної не будуть переглянутими. Якщо після цього залишаються не переглянуті вершини, вибирають одну з них і для неї процес обходу графа в глибину повторюється.

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

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