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