Алгоритмы на графах. Алгоритмы обхода графа

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

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

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

Ориентированный граф (орграф) – граф, у которого все ребра ориентированы, т.е. ребрам которого присвоено направление.

Неориентированный граф (неорграф) – граф, у которого все ребра неориентированы, т.е. ребрам которого не задано направление.

Смешанный граф – граф, содержащий как ориентированные, так и неориентированные ребра.

Петлей называется ребро, соединяющее вершину саму с собой. Две вершины называются смежными, если существует соединяющее их ребро. Ребра, соединяющие одну и ту же пару вершин, называются кратными.

Простой граф – это граф, в котором нет ни петель, ни кратных ребер.

Мультиграф – это граф, у которого любые две вершины соединены более чем одним ребром.

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

Маршрут называется открытым, если его начальная и конечная вершины различны, в противном случае он называется замкнутым.

Маршрут называется цепью, если все его ребра различны. Открытая цепь называется путем, если все ее вершины различны.

Замкнутая цепь называется циклом, если различны все ее вершины, за исключением концевых.

Граф называется связным, если для любой пары вершин существует соединяющий их путь.

Вес вершины – число (действительное, целое или рациональное), поставленное в соответствие данной вершине (интерпретируется как стоимость, пропускная способность и т. д.). Вес (длина) ребра – число или несколько чисел, которые интерпретируются по отношению к ребру как длина, пропускная способность и т. д.

Взвешенный граф – граф, каждому ребру которого поставлено в соответствие некое значение (вес ребра).

Выбор структуры данных для хранения графа в памяти компьютера имеет принципиальное значение при разработке эффективных алгоритмов. Рассмотрим несколько способов представления графа.

Пусть задан граф (например, рис 44.1), у которого количество вершин равно n, а количество ребер – m. Каждое ребро и каждая вершина имеют вес – целое положительное число. Если граф не является помеченным, то считается, что вес равен единице.

). Для его хранения обычно используют одномерный массив размером m, содержащий список пар вершин, смежных с одним ребром графа. Список ребер более удобен для реализации различных алгоритмов на графах по сравнению с другими способами.(рис 44.2) Граф(рис 44.1) Список ребер графа

(рис 44.3) Матрица смежности графа

(рис 44.4) Матрица инцидентности графа

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

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

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

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

Поиск в глубину

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

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

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

Шаг 1. Всем вершинам графа присваивается значение не посещенная. Выбирается первая вершина и помечается как посещенная.

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

Шаг 3. Повторить шаг 2 до тех пор, пока все вершины не будут помечены как посещенные (рис 44.5).

//Описание функции алгоритма поиска в глубину
void Depth_First_Search(int n, int **Graph, bool *Visited, 
                        int Node){
  Visited[Node] = true;
  cout << Node + 1 << endl;
  for (int i = 0 ; i < n ; i++)
    if (Graph[Node][i]  !Visited[i])
      Depth_First_Search(n,Graph,Visited,i);
}

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

Временная сложность зависит от представления графа. Если применена матрица смежности, то временная сложность равна O(n2), а если нематричное представление – O(n+m): рассматриваются все вершины и все ребра.

Поиск в ширину

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

Таким образом, основная идея поиска в ширину заключается в том, что сначала исследуются все вершины, смежные с начальной вершиной (вершина с которой начинается обход). Эти вершины находятся на расстоянии 1 от начальной. Затем исследуются все вершины на расстоянии 2 от начальной, затем все на расстоянии 3 и т.д. Обратим внимание, что при этом для каждой вершины сразу находятся длина кратчайшего маршрута от начальной вершины.

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

Шаг 1. Всем вершинам графа присваивается значение не посещенная. Выбирается первая вершина и помечается как посещенная (и заносится в очередь).

Шаг 2. Посещается первая вершина из очереди (если она не помечена как посещенная). Все ее соседние вершины заносятся в очередь. После этого она удаляется из очереди.

Шаг 3. Повторяется шаг 2 до тех пор, пока очередь не пуста (рис 44.6).

//Описание функции алгоритма поиска в ширину
void Breadth_First_Search(int n, int **Graph, 
                          bool *Visited, int Node){
  int *List = new int[n]; //очередь
  int Count, Head;        // указатели очереди
  int i; 
  // начальная инициализация
  for (i = 0; i < n ; i++)
    List[i] = 0;
  Count = Head = 0;
  // помещение в очередь вершины Node
  List[Count++] = Node;
  Visited[Node] = true;
  while ( Head < Count ) {
    //взятие вершины из очереди
    Node = List[Head++];
    cout << Node + 1 << endl;
    // просмотр всех вершин, связанных с вершиной Node
    for (i = 0 ; i < n ; i++)
      // если вершина ранее не просмотрена
      if (Graph[Node][i]  !Visited[i]){
        // заносим ее в очередь
        List[Count++] = i;
        Visited[i] = true;
      }
  }
}

Сложность поиска в ширину при нематричном представлении графа равна O(n+m), ибо рассматриваются все n вершин и m ребер. Использование матрицы смежности приводит к оценке O(n2)

Ключевые термины

Вес (длина) ребра – это число или несколько чисел, которые интерпретируются по отношению к ребру как длина, пропускная способность.

Вес вершины – это число (действительное, целое или рациональное), поставленное в соответствие данной вершине.

Взвешенный граф – это граф, каждому ребру которого поставлен в соответствие его вес.

Граф – это совокупность двух конечных множеств: множества точек и множества линий, попарно соединяющих некоторые из этих точек.

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

Замкнутый маршрут – это маршрут в графе, у которого начальная и конечная вершины совпадают.

Кратные ребра – это ребра, соединяющие одну и ту же пару вершин.

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

Матрица инцидентности – это двумерный массив, в котором указываются связи между инцидентными элементами графа (ребро и вершина).

Матрица смежности – это двумерный массив, значения элементов которого характеризуются смежностью вершин графа

Мультиграф – это граф, у которого любые две вершины соединены более чем одним ребром.

Неориентированный граф (неорграф) – это граф, у которого все ребра неориентированы, то есть ребрам которого не задано направление.

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

Ориентированный граф (орграф) – это граф, у которого все ребра ориентированы, то есть ребрам которого присвоено направление.

Открытый маршрут – это маршрут в графе, у которого начальная и конечная вершины различны.

Петля – это ребро, соединяющее вершину саму с собой.

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

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

Простой граф – это граф, в котором нет ни петель, ни кратных ребер.

Путь – это открытая цепь, у которой все вершины различны.

Ребра (дуги) графа – это множество линий, соединяющих вершины графа.

Связный граф – это граф, у которого для любой пары вершин существует соединяющий их путь.

Смежные вершины – это вершины, соединенные общим ребром.

Смешанный граф – это граф, содержащий как ориентированные, так и неориентированные ребра.

Список ребер – это множество, образованное парами смежных вершин

Тупик – это вершина графа, для которой все смежные с ней вершины уже посещены

Цепь – это маршрут в графе, у которого все ребра различны.

Цикл – это замкнутая цепь, у которой различны все ее вершины, за исключением концевых.

Краткие итоги

Лабораторная работа 44. Алгоритмы на графах. Алгоритмы обхода графа

Цель работы: изучить основные алгоритмы обхода графа и научиться решать задачи обхода графа на основе поиска в ширину и поиска в глубину.

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

Теоретические сведения.

Ознакомьтесь с материалом лекции 44.

Задания к лабораторной работе.

Выполните приведенные ниже задания.

Указания к выполнению работы.

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

Следует реализовать каждое задание в соответствии с приведенными этапами:

Требования к отчету.

Отчет по лабораторной работе должен соответствовать следующей структуре.

Контрольные вопросы