Шаг 195.
Основы языка Haskell. Реализация алгоритмов на графах... . Нерекурсивный алгоритм поиска в ширину на графе

    На этом шаге мы рассмотрим этот алгоритм.

    В приведённой ниже записи нерекурсивного алгоритма поиска в ширину на графе [1, с.125-126] предполагается, что:

   while (Имеется хотя бы одна непосещённая вершина)
   {
      Пусть p - первая из непосещённых вершин.
      Посетить вершину p и поместить её в пустую  очередь S;
      while (Очередь S непуста)
      {
        Пусть p - вершина, находящаяся на верхушке очереди S;
        if (Вершина p имеет непосещённые смежные вершины)
        {
          Пусть q - первая непосещённая вершина из вершин,
          смежных вершине p. Пройти по ребру (p,q), посетить
          вершину q и поместить её в очередь S
        }
        else Удалить вершину p из очереди S
      }
   }


   Замечание. Алгоритмы поиска в ширину на графе изложены в монографиях [2, с.198-205], [3, с.92-94].

(1)Касьянов В.H., Сабельфельд В.К. Сборник заданий по практикуму на ЭВМ. - М.: Наука, 1986. - 272 с.
(2)Пападимитриу Х., Стайнглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. - М.: Мир, 1985. - 512 с.
(3)Липский В. Комбинаторика для программистов. - М.: Мир, 1988. - 213 с.

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




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