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