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

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

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

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

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

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

Покажемо, що отримана таким чином послідовність дійсно задовольняє основній властивості топологічного сортування: якщо в графі існує ребро , то, у топологічному сортуванні його вершин, вершина  передує вершині . Для цього, припустимо противне, тобто нехай в графі  існує ребро  таке, що вершина  зустрічається в упорядкованій послідовності раніше вершини . Але тоді обробка вершини  була б завершена раніше, ніж обробка вершини . Це означає, що в момент закінчення обробки вершини , вершина  могла бути ще непройденою, або пройденою але не повністю сканованю. У першому випадку ми повинні були б пройти по ребру , але не зробили цього. У другому випадку пошук в глибину знайшов би зворотне ребро, тобто граф  містив би цикл. Обидва випадки приводять до протиріччя, а значить, наше припущення хибне і вказана послідовність вершин дійсно являється топологічним сортуванням розглядуваного графа .

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

Використовуючи алгоритм обходу графа в глибину знайти топологічне сортування для ациклічного орієнтованого графа наступного вигляду:

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

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

Дерево обходу в глибину заданого орієнтованого графа

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

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

Блок-схема алгоритму топологічного сортування орієнтованого графа