Шаг 86.
Построение остовного дерева связанного графа

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

    Обратимся теперь к задаче построения остовного дерева связного графа. Для этого вспомним, что при поиске в глубину новая вершина добавляется к списку уже пройденных вершин только в том случае, когда она в этом списке отсутствует. Поэтому последовательность вершин, соответствующая удлинению списка 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, что позволяет знать предшественника текущей вершины.


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

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




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