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

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

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

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

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

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

Нагадаємо, що за посиланням топологічне сортування вершин графа нами була розглянута одна з основних задач, що виникає при роботі з орієнтованими графами та один з методів для її рішення.

Задача про топологічне сортуванна графа

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

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

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

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