Алгоритмы поиска в графе. Поиск в глубину и в ширину. Классификация рёбер

Рис. 8

      При более подробном  рассмотрении  можно заметить, что  в случае  графа без петель матрица смежности имеет ряд особенностей:

        во-первых, главная  диагональ  матрицы всегда  заполнена нулями,  так как  вершина не может быть смежна  сама себе;

        во-вторых, если  наш граф  неориентированный - то часть матрицы  под главной  диагональю и над ней абсолютно идентичны.

Петля в матрице смежности может  быть представлена соответствующим  единичным диагональным элементом.

        На  Pascal-е  матрица  смежности, как   и матрица  инцидентности   чаще всего задается при помощи  двумерного массива:

 

        Matr_Sm :array [1..TopsCount,1..TopsCount] of  byte,

  либо

        Matr_Sm :array [1..TopsCount,1..TopsCount] of  boolean;

 

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

 

Список смежности

       

        Список смежности  представляет собой список из n строк, ( n -  количество вершин), где в i  - ой строке записываются номера вершин,  смежных с вершиной  под номером i. Как  мы видим,  этот список  тем  больше, чем больше связей между вершинами графа.

        Список  инцидентности   задается  аналогично  списку  смежности,  только  с одной   лишь разницей,  что в  i -  ой строке  записываются  номера ребер ( или дуг ), инцидентных данной ( i - ой ) вершине.

        Задание   графов  такими  способами   позволяет  более  экономно  расходовать память,  однако они  несколько  сложнее при реализации  и  обработке.  Из-за  того,  что  строки  в  списках   переменной длины,  появляется  необходимость  в использовании динамических  переменных и  указателей.   Рассмотрим  наиболее   тривиальную  реализацию   списка  смежности:

        Пусть задан   граф на n вершинах  и требуется создать некоторую структуру переменных в памяти ЭВМ,  отображающую список смежности, составленный  для  данного  графа.  Для  начала  выясним,  что будет  представлять собой данная структура.  Так как строка списка содержит  номера  вершин, то  естественно  предположить,  что мы  должны иметь  некоторую  цепочку  динамических   переменных  целочисленного  типа,  связанных  между  собой.  Такая  связь обеспечивается использованием  указателей, обьединенных вместе с  целочисленной переменной в запись  ( Pascal:  record ).  Для  того,  чтобы обеспечить  хранение входных  указателей   в   такие   цепочки,   используется  одномерный  массив  указателей, имеющий длину, равную количеству вершин графа. Признаком  конца цепочки можно использовать  какое либо значение, не допускаемое  при нумерации вершин ( например  - "0" ), занесенное в целочисленную переменную последнего блока. Например, для ориентированного графа на рис. 4  список смежности имеет следующий вид :     

1 - 2,3,4,0

2 - 3,0

3 - 0

4 - 3,0

                         

 

  Такой список будет представляться в памяти ЭВМ следующим образом (Рис. 9):

 

 

 

 

 

 

         

             

         

                   

 

     массив указателей   динамические переменные

    на входы в цепочки.   состоящие из указателя и

                                целочисленной переменной.

Рис. 9

 

        Для создания  такой структуры предварительно  необходимо сделать объявления  такого рода:

 

       Type

          BlockPtr  = ^BlockType;

          BlockType = record

                       Number :integer;

                       Point  :BlockPtr;

                      end;

 

       Var     In_Ptr :array [1..TopsCount] of BlockPtr;

        Создание  цепочки  в  памяти  осуществляется  при вводе списка  смежности  при  помощи  процедуры  New (BlockPtr_Type_Variable), где  BlockPtr_Type_Variable - переменная типа BlockPtr.

 

Поиск в графе.

 Алгоритм  поиска в глубину.

Структуры данных:

 списки

        Каждый    тип    списков    определяет    множество   конечных последовательностей  элементов, имеющий  заданный  базисный тип. Число  элементов  списка, называемое  его длиной,  в разных  списках одного  типа может быть различным.  Список, не имеющий элементов, называется  пустым. Для списка определены понятия начального, конечного и текущего  элементов, а также следующего и предыдущего элементов по отношению к  текущему.  Текущий элемент  - это  тот единственный  элемент списка,  который в данный доступен для обработки.

очередь  

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

        Набор базисных  операций над списками,  являющимися очередями,  состоит из четырех операций:

        1) Создание  пустой очереди;

 

        2) Проверка  очереди на пустоту;

 

        3) Выборки  первого  элемента из  очереди  с  одновременным его  удалением;

 

        4) Занесения   некоторого  значения базисного  типа в  качестве  нового последнего элемента очереди.

 

           стек  

        Стек  используется  для  реализации такой  дисциплины  обработки  элементов списка,  при которой элементы  списка  удаляются из  него в  порядке,  обратном порядку их занесения в стек  (т.е. по  принципу  "Последним пришел - первым ушел").

        Набор  базисных  операций  над  списками, являющимися  стеками,  состоит из пяти операций:

 

       

 

     

 

        1) Создание пустого стека;

 

        2) Проверка стека на пустоту;

 

        3,4) Выборки  последнего элемента из  стека  без удаления его из  стека  или с его удалением;

 

        5) Занесения   некоторого  значения базисного   типа в  качестве  нового  последнего элемента стека.

 

            деревья  

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

        Набор  базисных  операций  для  деревьев  состоит  из следующих  операций : Создание тривиального дерева по элементу базисного типа и  выборки или замены корня дерева  или списка его поддеревьев, а также  всех операций  (для списка поддеревьев),  которые являются базисными  для списка.

Обход графа в глубину

        При обходе дерева в глубину (известном также как прохождение в  прямом  порядке)   вершины  дерева  посещаются   в  соответствии  со  следующей рекурсивной процедурой: сначала  посетить корень дерева q;  затем если корень рассматриваемого дерева не является листом, то для  каждого сына  p корня q  рекурсивно обратиться к процедуре обхода в глубину для того, чтобы обойти все поддеревья с корнями p в порядке упорядоченности вершин p как сыновей корня q.   Если использовать стек S для хранения текущего пути по дереву,  т.е. пути, который начинается в  корне дерева и кончается в вершине,  посещаемой  в  данный  момент,   то  можно  построить  нерекурсивный  алгоритм для обхода дерева в глубину:

 

        Посетить корень  дерева и поместить его в  пустой стек S;

        WHILE стек S не является пустым DO

        BEGIN

         пусть p - вершина, находящаяся на верху стека S;

         IF сыновья  вершины p еще не посещались

            THEN посетить  старшего сына вершины  p и поместить его в

                 стек S

            ELSE BEGIN

                  удалить вершину p из стека S

                  IF p  имеет братьев THEN  посетить брата вершины p и

                                            поместить его в стек S

                 END

        END

 

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

 

        WHILE имеется  хотя бы одна не посещенная  вершина DO

        BEGIN

         пусть p - первая (т.е. минимальная) из не посещенных вершин;

         посетить  вершину p и поместить ее в пустой стек S;

         WHILE стек S не пуст DO

         BEGIN

          пусть p - вершина, находящаяся на верхушке стека S;

          IF у вершины p есть не посещенные смежные вершины

             THEN BEGIN

                   пусть  q -  первая не посещенная  вершина из вершин,

                   смежных вершине p;

                   пройти  по  ребру  (p,q),   посетить  вершину q  и

                   поместить ее в стек S;

                  END

             ELSE удалить вершину p из стека S

         END

        END

 

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

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

 

        Поместить  в стек исходную вершину графа  и пометить ее;

        WHILE стек не  пуст DO

         BEGIN

          извлечь  вершину из стека;

          IF есть  непомеченные вершины и смежные  с данной

           THEN пометить их и загрузить в  стек;

         END

 

 

Алгоритм поиска в ширину.

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

        Способ  обхода  дерева  в  ширину,  называемый  иногда способом  прохожде-ния  в горизонтальном  порядке, осуществляет посещение вершин  дерева слева направо, уровень за уровнем вниз от корня.

Приведенный  ниже алгоритм  реализует  обход  дерева в  ширину,  используя  две очереди O1 и O2.

 

      Взять пустые очереди O1 и O2;

        Поместить  корень в очередь O1;

        WHILE одна из очередей O1 и O2 не пуста DO

         IF O1 не является  пустой THEN

           BEGIN

            пусть p - вершина, находящаяся в голове очереди O1;

            посетить вершину p и удалить ее из O1;

            поместить всех сыновей вершины p  в очередь O2, начиная со

            старшего сына;

           END

          ELSE в  качестве  O1 взять непустую очередь  O2,  а в качестве

               O2 взять пустую очередь O1;

        Следует заметить,  что обход дерева поиска  в  ширину позволяет  обходить  дерево  поиска  одновременно   с  его  построением.  Таким  образом,  можно  решать  задачу  нахождения  какого-нибудь решения в  форме  вектора (а1, а2, ...)  неизвестной длины (не зная  r), если  только известно, что существует конечное решение задачи.

        Алгоритм  обхода графа  в ширину  аналогичен  алгоритму  обхода  дерева  в ширину,  за  исключением   использования метки  вершин, что  предохраняет алгоритм  от зацикливания.

        Алгоритм обхода  графа в ширину:

        Взять две  пустые очереди O1 и O2;

        Поместить  исходную вершину в очередь  O1 и пометить ее;

        WHILE очередь  O1 не пуста DO

         BEGIN

          посетить  вершину в голове очереди O1 и удалить ее из очереди;

          IF вершины  непомечены и смежны с данной

           THEN поместить их в очередь O2;

         END

 

Классификация рёбер графа

При поиске в глубину ребра графа  делятся на несколько категорий. Классификация ребер оказывается  полезной в различных задачах. Она  позволяет, например, распознать в графах циклы.