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

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

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

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

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

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

Зауваження: рішення, отримане при використанні алгоритму видалення вершини-джерела, може відрізнятися від рішення, яке дає алгоритм, що базується на пошуку в глибину. Звичайно, обидва вони коректні, просто задача про топологічне сортування може мати декілька різних рішень.

Задача про топологічне сортування графа – приклад розв’язання:

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

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

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

Орієнтований граф отриманий на першої ітерації

Після цього, перейшовши до ітерації номер два, виявляємо дві вершини, з нульовим напівстепенем заходу (число вхідних ребер). Це вершини «1» та «5» відповідно. Обравши одну з них, наприклад, вершну номер «1», видаляємо її разом з усіма інцидентними їй ребрами, для яких дана вершина являється початковою. В результаті отримаємо:

Орієнтований граф отриманий на другій ітерації

Продовжуємо ітераційний процес далі, і робимо це до тих пір поки не видалимо всі вершини заданого орієнтованого графа.

Орієнтовані графи отримані на третій, четвертій, п’ятій та шостій ітераціях відповідно

На останньому кроці, скориставшись порядком, в якому здійснювалось видалення вершин (), отримаємо розв’язок задачі про топологічгне сортування.

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

Залишити коментар

Your email address will not be published. Required fields are marked *

*