Материал: 62_201
1 |
0 |
0 |
0 |
0 |
0 |
1 |
2 |
1 |
0 |
0 |
1 |
0 |
0 |
3 |
1 |
1 |
0 |
0 |
0 |
1 |
4 |
0 |
0 |
0 |
0 |
0 |
0 |
5 |
0 |
0 |
0 |
0 |
0 |
0 |
6 |
0 |
0 |
0 |
0 |
1 |
0 |
б)
Мал. 40
на малюнку 41, а. Для фіксації переглянутих вершин, згідно з алгоритмом пошуку в глибину, використовуватимемо множи ну, куди на першому кроці запишемо вершину 1. Відповідно до таблиці суміжності вона має ребро з вершиною 6. Перейдемо до неї, записавши наступною в послідовності переглянутих вер шин (мал. 41, в).
З вершини 6 далі ми можемо рухатися лише у вершину 5. Дописуємо її в множину й в послідовність переглянутих вер шин (мал. 41, в).
Мал. 41
Вершина 5 є тупиковою, тому визначимо її як елемент тополо гічного сортування вершин графа і зафіксуємо її номер у другому рядку на малюнку 42, а. Повернемося до попередньої вершини у послідовності переглянутих вершин, якою є вершина 6. Верши на 6 також є тупиковою, оскільки, окрім вершини 5, ніяких інших
82
Мал. 42
вершин з неї не видно. Виведемо її в другий рядок (мал. 42, б). Переходимо до вершини 1, яка також заводить нас у тупик. Фіксуємо її як елемент топологічного сортування і вилучаємо
зпослідовності переглянутих вершин (мал. 42, в). Послідовність переглянутих вершин вичерпано, але ще не
всі вершини графа переглянуті. Тому продовжимо наш пошук далі. Наступною вершиною логічно розглянути вершину 2: в ній ми ще не були і її номер наступний за значенням. Запише мо її в послідовність переглянутих вершин на першу позицію і занесемо в множину (мал. 43, а).
З вершини 2 першою можна побачити вершину 1. Але пере ходити в неї не можна, оскільки ми вже в ній побували. На ступною за значенням вершиною, в яку можна перейти з 2, є 4. Вона нова, тому здійснимо цей крок (мал. 43, б). Тепер уже вер шина 4 стає тупиком. Перенесемо її в топологічно відсортовану послідовність і перейдемо до вершини 2 (мал. 43, в).
Мал. 43
83
Мал. 43 (продовження)
Вершина 2 - тупикова. Перепишемо її номер у другий ря док, а наша послідовність переглянутих вершин (перший ря док) знову стає порожньою (мал. 44, а). Оскільки ще не всі вер шини нашого графа переглянуті, то доводиться шукати наступ ну нову вершину. Такою є вершина 3. Запишемо її першою у послідовність переглянутих вершин і занесемо в множину (мал. 44, а).
З вершини 3 хоча і є ребра до трьох вершин - 1,2,6, однак вони вже всі були переглянуті, тому це тупик. Згідно з нашим алго ритмом ми фіксуємо вершину 3 як останній елемент у тополо гічно відсортованій послідовності і повертаємо до попереднього елемента у послідовності переглянутих верпіин (мал. 44, в). Це останній крок алгоритму, оскільки всі вершини переглянуті і послідовність переглянутих вершин вичерпано.
У другому рядку на малюнку 44, в міститься результат ви конання алгоритму топологічного сортування у зворотному
Мал. 44
84
Мал. 45
порядку. Зобразимо нашу відповідь 3, 2, 4, 1, 6, 5, де вказано ребра, які існують між цими вершинами в заданому графі (мал. 45). Як бачимо, умова топологічного сортування вершин графа виконується.
А тепер реалізація запропонованого алгоритму мовою про грамування:
|
{Ініціалізація початку роботи програми:} |
top := 1; а[1] := k; |
{top - вершина стеку; а - стек,} |
|
{s - множина відвіданих вершин;} |
s := [k]; count := 0; і := 1; |
{count- лічильник сортування.} |
while (top > 0) Or (s <> [1 ..n]) do {Пошук нових невідвіданих вершин графа.}
begin
while (І <= n) do |
{Пошук ребра, яке веде у нову невідвідану вершину.} |
|
begin |
|
|
if (d[a[top], І]=1) and not (І in s) |
{Якщо таке існує, то} |
|
then |
|
|
begin |
|
|
inc(top); a[top] := і; |
{запис нової вершини у стек} |
|
s := s + [і]; і := 1; |
|
{і у множину.} |
end |
|
|
else Іпс(і) |
|
{Перехід до наступної вершини.} |
end; |
|
|
{Якщо поточна вершина є тупиковою,} inc(count); sort[count] :=a[top]; {то запис її у відсортовану послідовність}
dec(top); |
|
{і зменшення значення вершини стеку.} |
if (top = 0) and (s <> [1 ..n]) |
{Якщо стек порожній, але не всі вершини} |
|
then |
|
{графа відвідані, то} |
begin |
|
|
І := 1; |
{пошук нової стартової вершини для продовження обходу графа:} |
|
while І in S do Іпс(і); |
{вибір нової невідвіданої вершини;} |
|
inc(top); a[top] := і; |
{запис її у стек} |
|
s := s + [ і ] ; і := 1; |
{і у множину відвіданих вершин;} |
|
end |
|
{початок пошуку існуючих ребер з цієї вершини.} |
else і := 1; {Стек не порожній - початок пошуку існуючих ребер з поточної вершини.}
end;
До розв'язання сформульованої задачі щодо топологічного сортування вершин ациклічного орієнтованого графа можна підійти ще міркуючи так. Нехай граф задано не таблицею су міжності, а послідовністю ребер цього графа. Наприклад, граф, зображений на малюнку 39, а, може бути описаний такою послідовністю ребер:
85
3 2
2 1
24
16
36
6 5
3 1 Оскільки представлений граф є орієнтованим, то опис кожно
го ребра вказує його напрям: перша вершина в указаній парі - це початок ребра, тобто вихідна вершина, а друга - його кінець, або вхідна вершина. Розглянемо номери вершин, що є вхідни ми, тобто другий стовпчик у вхідній інформації про заданий граф. У ньому вказано номери вершин, у які входять ребра, тобто ці вершини є нащадками тих вершин, які вказані як від повідні вихідні. А що можна сказати про номери вершин, які не зафіксовані як вхідні? Це ті вершини, які не є нащадками, а значить, вони самі можуть мати лише нащадків. Для нашого прикладу такою є вершина 3. Виведемо її першою під час топо логічного сортування. Оскільки вершина 3 нами вже опрацьо вана, приберемо в графі ребра, які з неї виходять (мал. 46, а). Відповідно скоректуємо вхідну інформацію, вилучивши ті реб ра, які мають вихідними вершинами вершину 3. Подивимося знову на граф і визначимо, які вершини тепер не є нащадками. У другому стовпчику скоректованої вхідної інформації з'яви лася ще одна відсутня вершина 2. Це означає, що тепер вона не має нащадків і можна її записувати слідом за вершиною 3 у то пологічно відсортовану послідовність та вилучити ребра, у яких вершина 2 є вихідною (мал. 46, б).
Проаналізуємо нові відсутні ребра у графі, зображеному на малюнку 46, б. Тепер там немає вершин 1 та 4. Проведемо про цедуру, аналогічну до попередньої, з вершинами 1 і 4 (мал. 46, в). Тепер у нас залишилося тільки одне ребро (6,5). Новою відсутньою вершиною, що відіграє роль вхідної, є вершина 6. Вилучаємо останнє ребро, що залишилося в нас у списку ребер графа, і записуємо вершину 6 у топологічно відсортовану послі-
"$v
21
"ОЗ 24 16 65
а) 5«
Мал. 46
86