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

Обратимся теперь к задаче построения остовного дерева связного графа. Для этого вспомним, что при поиске в глубину новая вершина добавляется к списку уже пройденных вершин только в том случае, когда она в этом списке отсутствует. Поэтому последовательность вершин, соответствующая удлинению списка PATH при работе функции DEFI, представляет собой простой (т.е. без самопересечений) путь в просматриваемом графе.

После этих замечаний можно написать функцию, значением которой является список ребер, представляющий остовное дерево графа. Программа [1, с.130-131].

   (DEFUN SPANDF (LAMBDA (GRAPH ROOT)
   ; GRAPH - граф в виде структуры смежности               ;
   ; ROOT  - корень остовного дерева                       ;
   ; Результат: список ребер остовного дерева, полученного ;
   ;              с помощью поиска в глубину               ;
      (COND ( (NULL GRAPH) NIL )
            (  T  (SPDF GRAPH (LIST ROOT) (LIST ROOT)) )
      )
   ))
   ; ------------------------------------ ;
   (DEFUN SPDF (LAMBDA (GRAPH VISITED PATH)
   ; VISITED - список уже просмотренных вершин            ;
   ; PATH    - список вершин, определяющий путь просмотра ;
      (COND ( (NULL PATH) NIL )
            (  T  (COND ( (NULL (EXPND GRAPH VISITED
                                       (CAR PATH)))
                             (SPDF GRAPH VISITED (CDR PATH))
                        )
                        (  T  (CONS
                                  (CONS (CAR PATH)
                                        (EXPND GRAPH VISITED
                                               (CAR PATH)))
                                  (SPDF
                                      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)) )
      )
   ))

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

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

   $ (SPANDF '((1 . (2 3)) (2 . (4 5)) (3 . (6 7))) 1)
   ((1 . 2) (2 . 4) (2 . 5) (1 . 3) (3 . 6) (3 . 7))

Теперь мы зададимся вопросом, какими свойствами будет обладать остовное дерево, построенное с помощью процедуры поиска в ширину? Мы уже упоминали о том, что при поиске в ширину просмотренные вершины располагаются в порядке неубывания их расстояния от начальной вершины. Поэтому в остовном дереве, построенном с помощью поиска в ширину, единственный путь, соединяющий какую-либо вершину с начальной, совпадает с кратчайшим путем в исходном графе между этими двумя вершинами.

Необходимые для построения остовного дерева с помощью поиска в ширину изменения в функции BRFI более существенны по сравнению с аналогичными изменениями в функции DEFI. Дело в том, что при поиске в ширину нам не нужна была информация о предшественнике рассматриваемой вершины - в этом смысле поиск в ширину нелокален. Поэтому вместо очереди вершин, предназначенных для просмотра, мы введем очередь, состоящую непосредственно из элементов структуры смежности.

Программа [1, с.132-133].

   (DEFUN SPANBF (LAMBDA (GRAPH ROOT)
   ; GRAPH - граф в виде структуры смежности ;
   ; ROOT  - корень остовного дерева         ;
   ; Результат: остовное дерево              ;
      (SPBF GRAPH (LIST ROOT) (CDR (ASSOC ROOT GRAPH))
            NIL (CAR (ASSOC ROOT GRAPH)))
   ))
   ; ------------------------------------------------- ;
   (DEFUN SPBF (LAMBDA (GRAPH VISITED HEAD QUEUE FATHER)
   ; QUEUE - очередь списков вершин для просмотра ;
   ; HEAD  - список вершин для просмотра          ;
   ; FATHER - предок просматриваемых вершин       ;
      (COND ( (NULL HEAD)
                 (COND ( (NULL QUEUE) NIL )
                       (  T  (SPBF GRAPH VISITED
                                   (CDAR QUEUE) (CDR QUEUE)
                                   (CAAR QUEUE)) )
                 )
            )
            ( T  (COND ( (MEMBER (CAR HEAD) VISITED)
                            (SPBF GRAPH VISITED
                                  (CDR HEAD) QUEUE
                                  FATHER) )
                       (  T  (CONS
                                 (CONS FATHER (CAR HEAD))
                                 (SPBF
                                    GRAPH
                                    (CONS (CAR HEAD) VISITED)
                                    (CDR HEAD)
                                    (APPEND
                                       QUEUE
                                       (LIST (ASSOC (CAR HEAD)
                                                    GRAPH)))
                                    FATHER)) )) )
      )
   ))

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

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

   $ (SPANBF '((1 . (2 4)) (2 . (1 3)) (4 . (1 3)) (3 . (1 4))) 1)
   ((1 . 2) (1 . 4) (2 . 3))
   $ (SPANBF '((1 . (2 4)) (2 . (1 3)) (4 . (1 3)) (3 . (1 4))) 2)
   ((2 . 1) (2 . 3) (1 . 4))
   $ (SPANBF '((1 . (2 4)) (2 . (1 3)) (4 . (1 3)) (3 . (1 4))) 3)
   ((3 . 1) (3 . 4) (1 . 2))
   $ (SPANBF '((1 . (2 4)) (2 . (1 3)) (4 . (1 3)) (3 . (1 4))) 4)
   ((4 . 1) (4 . 3) (1 . 2))
   $ (SPANBF '((1 . (2 3)) (2 . (4 5)) (3 . (6 7))) 1)
   ((1 . 2) (1 . 3) (2 . 4) (2 . 5) (3 . 6) (3 . 7))

Обратите внимание, что при работе функции SPBF параметр HEAD всегда есть список соседей вершины, определяемой параметром FATHER, что позволяет знать предшественника текущей вершины.

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

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

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