Компьютерная математика: Часть 2. Теория графов. Волченская Т.В - 81 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

‘
Нахождение отображений и транзитивных замыканий’
Приложение 2
Построение транзитивных замыканий
Обозначения:
X - номер вершины для которой ищется транзитивное замыкание;
T(N) - массив транзитивного замыкания;
С - счетчик добавления вершин в транзитивное замыкание ;
P - признак: P = 1 при формировании Т
+
, P = 0 при формировании Т
-.
TRAN
L = 1
I=1,N
T[I]=L
Нет
Да
T[X]=
L
C = 0
∗
J=1,N
∗
P=1
Да
Да
A[i,j]=1
A[j,i]=1
T[j]=0
T[j]=L+1
Нет
Нет
Да
C=0
L =
L1
Нет
RETURN
Нет
Да
C=C+1 
                               Приложение 2
                  Построение транзитивных замыканий
                             Обозначения:
X - номер вершины для которой ищется транзитивное замыкание;
T(N) - массив транзитивного замыкания;
С - счетчик добавления вершин в транзитивное замыкание ;
P - признак: P = 1 при формировании Т+ , P = 0 при формировании Т-.

                      TRAN


                      L=1

                     T[X]=
                       L
                      C=0

                     I=1,N


    ∗        Нет     T[I]=L

                         Да
                     J=1,N          ∗
             Да
                       P=1



    Нет                  Нет
          A[i,j]=1             A[j,i]=1

              Да                    Да


    Нет
           T[j]=0                           C=0
                                      Нет
          T[j]=L+1                          L=
                                            L 1
          C=C+1

                                            RETURN




‘Нахождение отображений и транзитивных замыканий’

Страницы