Методи програмування

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

Загальна інформація

Завдання складається з двох частин, перша з яких є обов'язковими для виконання, друга виконується для отримання оцінки «відмінно».

Бінарним ставленнямна множині A називатимемо підмножину декартового твору M x M , тобто. кілька упорядкованих пар, кожен елемент яких є елементом множини A . Наприклад, ставлення > (Більше) є бінарним ставленням на безлічі і містить пари (2, 1), (3, 1), (4, 1), (3, 2), (4, 2), (4, 3) . Будемо говорити, що істинно твердження a R b якщо пара (a, b) належить бінарному відношенню R .

Нехай дано деяке бінарне відношення R на кінцевій множині A . Завданням топологічного сортування є вибудовування елементів множини A послідовність a1, a2, . aN так, що для будь-якої пари (ai, aj) такої, що істинно ai R aj виконується умова i .

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

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

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

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

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

Формулювання завдання

a. Реалізація на матрицях суміжності.

У вхідному файлі input.txt вводиться графік у вигляді списку ребер. Вважати його в матрицю суміжності (двовимірний масив, елемент (i, j) якого дорівнює 1 якщо у графі є ребро з вершини i у вершину j і 0 в іншому випадку) і виконати топологічне сортування цього графа. Результат (послідовність вершин або повідомлення про наявність циклу у графі) видати у файл output.txt.

b. *Реалізація на списках суміжності.

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