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

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

topologichne_sortuvannja_grafa28

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

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

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