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