Page 32 - 4336

2.3.2 Знаходження зворотного транзитивного замикання

Алгоритм знаходження зворотного транзитивного

замикання по матриці суміжності A для вершини v полягає в
i
наступному.

-
Крок 1. Формується вектор Т (v ) з n елементів, де n –
i
кількість вершин графа. Даний вектор визначає довжини шляхів

від усіх вершин графа до i-ї вершини. Приймається d=0. В i-й
-
елемент вектора Т (v ) заноситься значення d. j=i.
i i
Крок 2. Переглядається j-й стовпчик матриці суміжності A і

визначаються елементи a (i=1, 2, …, n) рівні 1.
i,j
Крок 3. Якщо жодний з елементів a ≠1, то алгоритм
i,j
-
завершується. Усім незаповненим елементам вектора Т (v )
i
присвоюється значення ∞ – це означає що від даних вершин

графа немає шляхів до вершини v . В іншому випадку
i
здійснюється перехід до кроку 4.

Крок 4. Якщо є один або більше елементів a =1, то d=d+1,
i,j
j=i (крім тих значень i, яким відповідають уже заповнені
-
елементи вектора Т (v )) та відповідним i-м елементам вектора
i
-
Т (v ) (крім уже заповнених елементів) присвоюється значення d.
i i
Це означає що від даних вершин існують шляхи довжиною d до
-
вершини v . Якщо усі елементи вектора Т (v ) заповнені, то
i
i
алгоритм завершує свою роботу. В іншому випадку здійснюється

перехід до кроку 5.

Крок 5. Переглядаються відповідні j-ті стовпчики матриці

суміжності A і визначаються елементи a (i=1, 2, …, n) рівні 1.
i,j
Здійснюється перехід до кроку 3.

Приклад 2.6. Знайти зворотне транзитивне замикання по

матриці суміжності, наведеної на рис. 2.2, а, для вершини v
3
графа, наведеного на рис. 2.2, б.

32