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

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

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

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

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

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

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

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

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

topologichne_sortuvannja_grafa28

Орієнтований граф та один з варіантів топологічного сортування його вершин

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

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