Топологічне сортування вершин орієнтованого графа методом видалення вершини-джерела в середовищі програмування delphi

Топологічне сортування — це сортування елементів, для яких визначено частковий порядок, тобто впорядкування задано не на всіх, а тільки на деяких парах елементів. Крім того, це однин з основних алгоритмів на графах, який застосовується для вирішення більш складних задач.

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

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

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

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

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

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

Далі, скориставшись кнопкою «Топологічне сортування орієнтованого графа» визначимо один з варіантів лінійного порядку вершин заданого графи, при якому всі його ребра йдуть зліва направо.

Топологічний порядок вершин заданого орієнтованого графа

Скачати delphi-проект Топологічне сортування вершин орієнтованого графа методом видалення вершини-джерела.

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

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