Нагадаємо, що за посиланням топологічне сортування вершин графа нами була розглянута одна з основних задач, що виникає при роботі з орієнтованими графами та один з методів для її рішення.
Топологічне сортування графа методом видалення вершини-джерела
Сьогодні, для розв’язку задачі такого типу, застосуємо дещо інший алгоритм, заснований на безпосередній реалізації методу зменшення розміру задачі, а якщо бути більш точним, то зменшенням розміру на одиницю.
Основна суть даного алгоритму полягаєв в тому, що на кожній з його ітерацій, здійснюється визначення вершини-джерела орієнтованого графа що залишився (джерелом називається вершина в яку не входить жодне ребро), і, в подальшому, видалення його з усіма, що виходять з нього, ребрами. Якщо таких вершин декілька, довільним чином вибирається одна з них. Порядок видалення таким чином вершин, дає рішення задачі про топологічне сортування. Відмітимо, що якщо на деякому кроці виявиться, що для орієнтованого графа що залишився, вершини-джерела не існує, то задача про тополігічне сортування розв’язків немає.
Зауваження: рішення, отримане при використанні алгоритму видалення вершини-джерела, може відрізнятися від рішення, яке дає алгоритм, що базується на пошуку в глибину. Звичайно, обидва вони коректні, просто задача про топологічне сортування може мати декілька різних рішень.
Задача про топологічне сортування графа – приклад розв’язання:
Використовуючи метод видалення вершини-джерела знайти топологічне сортування для орієнтованого графа, що міститься на наступному малюнку.
Орієнтований граф задачі
Для цього, на першому кроці, серед вершин заданого графа вибираємо ту, в яку не входить жодне з його орієнтованих ребер. В нашому випадку, такою являється вершина номер «4». Видаляємо її разом з усіма що виходять з неї ребрами. В результаті, заданий орієнтований граф прийме наступного вигляду:
Орієнтований граф отриманий на першої ітерації
Після цього, перейшовши до ітерації номер два, виявляємо дві вершини, з нульовим напівстепенем заходу (число вхідних ребер). Це вершини «1» та «5» відповідно. Обравши одну з них, наприклад, вершну номер «1», видаляємо її разом з усіма інцидентними їй ребрами, для яких дана вершина являється початковою. В результаті отримаємо:
Орієнтований граф отриманий на другій ітерації
Продовжуємо ітераційний процес далі, і робимо це до тих пір поки не видалимо всі вершини заданого орієнтованого графа.
Орієнтовані графи отримані на третій, четвертій, п’ятій та шостій ітераціях відповідно
На останньому кроці, скориставшись порядком, в якому здійснювалось видалення вершин (), отримаємо розв’язок задачі про топологічгне сортування.