На этом шаге мы рассмотрим алгоритм вычисления компонент связности.

С помощью поиска на графе можно ответить на некоторые вопросы относительно структуры графа. Мы рассмотрим здесь две задачи, связанные с поиском:

Для вычисления компонент связности графа воспользуемся уже написанной функцией DEPTHFIRST. Рассмотрим еще раз работу функции DEFI. Заметим, что когда к списку просмотренных вершин VISITED добавляется новая вершина, список PATH представляет собой путь из этой вершины в начальную. Поэтому по окончанию работы в списке VISITED содержатся только те вершины, которые можно соединить с начальной. Можно показать [2], что в этом списке содержатся все вершины, обладающие этим свойством.

Таким образом, можно сказать, что функция DEPTHFIRST вычисляет список вершин связной компоненты вершины ROOT, и теперь мы готовы решить задачу о построении всех компонент связности данного графа.

Проще всего это сделать в два этапа.

Сначала построим списки вершин компонент связности. Программа [1, с.129-130].

   (DEFUN CONNLISTS (LAMBDA (GRAPH)
   ; GRAPH - граф в виде структуры смежности              ;
   ; Результат: список списков вершин компонент связности ;
      (CONNLSTS GRAPH NIL)
   ))
   ; --------------------------------- ;
   (DEFUN CONNLSTS (LAMBDA (GRAPH LISTS)
      (COND ( (NULL GRAPH) LISTS )
            ( T (COND ( (NULL (LMEMBER (CAAR GRAPH) LISTS))
                           (CONNLSTS
                               (CDR GRAPH)
                               (CONS (DEPTHFIRST
                                         GRAPH
                                         (CAAR GRAPH))
                                     LISTS)
                           )
                      )
                      (  T  (CONNLSTS (CDR GRAPH) LISTS) )
                )
            )
      )
   ))
   ; --------------------------------- ;
   (DEFUN LMEMBER (LAMBDA (VERTEX LISTS)
   ; Проверяет, содержится ли вершина VERTEX в каком-либо ;
   ;          из списков, составляющих LISTS              ;
      (AND
          LISTS
          (OR (MEMBER  VERTEX (CAR LISTS))
              (LMEMBER VERTEX (CDR LISTS))
          )
      )
   ))
   ; ---------------------------------- ;
   (DEFUN DEPTHFIRST (LAMBDA (GRAPH ROOT)
   ; GRAPH - граф в виде структуры смежности              ;
   ; ROOT  - вершина графа, с которой начинается поиск    ;
   ; Результат: список вершин графа в порядке прохождения ;
      (COND ( (NULL GRAPH) NIL )
            (  T  (DEFI GRAPH (LIST ROOT) (LIST ROOT)) )
      )
   ))
   ; ------------------------------------ ;
   (DEFUN DEFI (LAMBDA (GRAPH VISITED PATH)
   ; VISITED - список уже просмотренных вершин         ;
   ; PATH - список вершин, определяющих путь просмотра ;
      (COND ( (NULL PATH) (REVERSE VISITED) )
            ( T  (COND ( (NULL (EXPND GRAPH VISITED (CAR PATH)))
                            (DEFI GRAPH
                                  VISITED
                                  (CDR PATH))
                       )
                       (  T  (DEFI GRAPH
                                   (CONS (EXPND GRAPH VISITED
                                                (CAR PATH))
                                         VISITED)
                                   (CONS (EXPND GRAPH VISITED
                                                (CAR PATH))
                                         PATH))
                       )
                 )
            )
      )
   ))
   ; --------------------------------------- ;
   (DEFUN EXPND (LAMBDA (GRAPH VISITED VERTEX)
   ; Выбор следующей еще не просмотренной вершины, ;
   ;               соседней с VERTEX               ;
      (COND ( (NULL (NEIGHBOUR3 VERTEX GRAPH)) NIL )
            (  T  (FIRSTNOTVISITED
                             VISITED
                             (NEIGHBOUR3 VERTEX GRAPH))
            )
      )
   ))
   ; ------------------------------------------ ;
   (DEFUN FIRSTNOTVISITED (LAMBDA (VISITED VLIST)
      (COND ( (NULL VLIST) NIL )
            (  T  (COND ( (NULL (MEMBER (CAR VLIST) VISITED))
                             (CAR VLIST) )
                        (  T  (FIRSTNOTVISITED
                                           VISITED
                                           (CDR VLIST)) )
                  )
            )
      )
   ))
   ; ------------------------------- ;
   (DEFUN NEIGHBOUR3 (LAMBDA (X GRAPH)
      (COND ( (NULL (ASSOC X GRAPH)) NIL )
            (  T  (CDR (ASSOC X GRAPH)) )
      )
   ))

Текст этой библиотеки можно взять здесь.

Тестовые примеры:

   $ (CONNLISTS '((1 . (2 3)) (2 . (3)) (5 . ())))
   ((5) (1 2 3))
   $ (CONNLISTS '((1 . (2 3)) (2 . (3)) (5 . ()) (6 . ()))
   ((6) (5) (1 2 3))
   $ (CONNLISTS '((1 . (2 3)) (2 . (3)) (5 . (6))))
   ((5 6) (1 2 3))
   $ (CONNLISTS '((1 . (2 3 5)) (2 . (3)) (5 . (6))))
   ((1 2 3 5 6))

Теперь не составляет труда написать функцию, вычисляющую сами компоненты связности, представленные в виде структур смежности. Для этого мы воспользуемся следующими вспомогательными функциями, позволяющими выделить компоненты связности:

   (DEFUN F2 (LAMBDA (GRAPH LST)
      (COND ( (NULL LST) NIL )
            (  T  (CONS (F1 GRAPH (CAR LST))
                        (F2 GRAPH (CDR LST))) )
      )
   ))
   ; ------------------------- ;
   (DEFUN F1 (LAMBDA (GRAPH LST)
      (COND ( (NULL GRAPH) NIL )
            ( (MEMBER (CAAR GRAPH) LST)
                 (CONS (CAR GRAPH) (F1 (CDR GRAPH) LST)) )
            (  T  (F1 (CDR GRAPH) LST) )
      )
   ))

Текст этой библиотеки можно взять здесь.

Тестовый пример:

   $ (F2 '((1 . (2 3)) (4 . (5 6)) (5 . (4)) (3 . (2 1)))  '((1 2 3) (4 5 6)))
   (((1 2 3) (3 2 1) ((4 5 6) (5 4)))

⁽¹⁾ Крюков А.П., Радионов А.Я., Таранов А.Ю., Шаблыгин Е.М. Программирование на языке R-Лисп. - М.: Радио и связь, 1991. - 192 с.
⁽²⁾ Липский В. Комбинаторика для программистов: Пер. с польск. - М.: Мир, 1988. - 213 с.

На следующем шаге мы рассмотрим построение остовного дерева связного графа .

Предыдущий шаг Содержание Следующий шаг