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

Обход графа в ширину. Кратчайшие пути. Алгоритм Дейкстры

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

Превратим обход в ширину в алгоритм Дейкстры за (n * log(n) + m * log(n))!
Данная статься предназначена в основном для участников div2, но я так же надеюсь, что и некоторым немного более продвинутым программистам будет интересно почитать.

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

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

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

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

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

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

Для наглядного представления, приведу картинку.

Здесь мы начали обходить граф в ширину из вершины C. Затем мы перешли к рассмотрению вершин A, B и E.

Реализация обхода в ширину

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

void bfs(int u) { used[u] = true; queue q; q.push(u); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < (int) g[u].size(); i++) { int v = g[u][i]; if (!used[v]) { used[v] = true; q.push(v); } } }}

В этой реализации g — это список смежных вершин, т.е. в g[u] лежит список смежных вершин с u(в качестве списка использован std::vector), used — это массив, который позволяет понять, в каких вершинах мы уже побывали. Здесь обход в ширину не делает ничего, кроме самого обхода в ширину.

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

void bfs(int u) { used[u] = true; p[u] = u; dist[u] = 0; queue q; q.push(u); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < (int) g[u].size(); i++) { int v = g[u][i]; if (!used[v]) { used[v] = true; p[v] = u; dist[v] = dist[u] + 1; q.push(v); } } }}

Здесь p — это массив предков, т.е. в p[v] лежит предок вершины v, dist[v] — это расстояние от вершины из которой мы начинали обход, до вершины v. Как восстановить путь? Это сделать довольно легко, просто пройдя по массиву предков нужной нам вершины. Например, рекурсивно:

void print_way(int u) { if (p[u] != u) { print_way(p[u]); } cout dist[u] + len) { p[v] = u; dist[v] = dist[u] + len; q.push(v); } } }}

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

const int INF = 1e+9; vector< pair > g[LIM];bool inque[LIM]; void shortcut(int u) { fill(dist, dist + n, INF); dist[u] = 0; p[u] = u; queue q; q.push(u); inque[u] = true; while (!q.empty()) { int u = q.front(); q.pop(); inque[u] = false; for (int i = 0; i < (int) g[u].size(); i++) { int v = g[u][i].second, len = g[u][i].first; if (dist[v] > dist[u] + len) { p[v] = u; dist[v] = dist[u] + len; if (!inque[v]) { q.push(v); inque[v] = true; } } } }}

Если присмотреться, то этот алгоритм очень похож на алгоритм Левита, но все-таки это не он, хотя в худшем случае работает за ту же ассимтотику. Давайте грубо оценим это. В худшем случае нам придется проводить релаксацию каждый раз, когда мы проходим по какому-либо ребру. Итого O(n * m).

Оценка довольно грубая, но на начальном этапе этого вполне хватит. Стоит так же заметить, что это именно худший случай, а на практике даже такая реализация работает довольно быстро. А теперь, самое интересное! …барабанная дробь…

Улучшим наш алгоритм до алгоритма Дейксты!

Алгоритм Дейкстры

Первая оптимизация, которая приходит на ум. А давайте релаксировать те вершины, путь до которой сейчас минимальный? Собственно, именно эта идея и пришла мне в один прекрасный день в голову. Но, как оказалось, эта идея пришла первому далеко не мне. Первому она пришла замечательному ученому Дейкстре.

Более того, именно он доказал, что выбирая вершину для релаксации таким образом, мы проведем релаксацию не более, чем n раз! На интуитивном уровне понятно, что если до какой-то вершины путь сейчас минимальный, то еще меньше сделать его мы не сможем.

Более формально можно прочитать на замечательном сайте e-maxx(Дружно говорим спасибо Максиму e-maxx Иванову) или на Википедии.
Теперь дело осталось за малым, понять как эффективно искать вершину с минимальным расстоянием до нее. Для этого воспользуемся очередью с приоритетами(куча, heap).

В stl есть класс, который реализует ее и называется priority_queue. Приведу реализацию, которая, опять же, напрямую следует из предыдущего(описанного в этой статье) алгоритма.

void deikstra(int u) { fill(dist, dist + n, INF); dist[u] = 0; p[u] = u; priority_queue< pair, vector< pair >, greater< pair > > q; q.push(make_pair(0, u)); while (!q.empty()) { pair u = q.top(); q.pop(); if (u.first > dist[u.second]) continue; for (int i = 0; i < (int) g[u.second].size(); i++) { int v = g[u.second][i].second, len = g[u.second][i].first; if (dist[v] > dist[u.second] + len) { p[v] = u.second; dist[v] = dist[u.second] + len; q.push(make_pair(dist[v], v)); } } }}

Скорее всего не совсем понятно, что здесь происходит. Начнем с объявления очереди с приоритетами.

Здесь первый аргумент шаблона — данные, которые хранятся в очереди, а конкретно пары вида (расстояние до вершины, номер вершины), второй аргумент шаблона — это контейнер, в котором будут храниться данные, третий аргумент, компоратор(находится, кстати, в заголовочном файле functional).

Почему нам нужен какой-то другой компоратор? Потому что при стандартном обявлении priority_queue< pair >, доставать получится только те вершины, расстояние до которых максимально, а нам-то нужно совсем наоборот.

Есть и другой способ, который предлагает e-maxx, будем хранить отрицательные значения длин, а при вытаскивании длины из очереди умножать на -1(подробнее прочитать можно здесь). Ассимптотика такого решения поставленной задачи O(n * log(n) + m * log(n)).

Действительно, всего у нас n релаксаций, а вершину с минимальной длиной пути до нее, мы ищем за log(n)(именно такая ассимптотика у стандартной очереди с приоритетами stl). Так же следует заметить, что у нас может получится так, что мы добавили в очередь одну и ту же вершину, но с разными путями до нее.

Например, мы провели релаксацию из вершины A, у которой в соседях вершина C, а потом провели релаксацию из вершины B, у которой так же в соседях вершина C, для ухода от проблем, связанных с этим, будем просто пропускать те вершины, которые мы достали из очереди, но расстояние из очереди до которых не актуально, т.е. больше, чем текущее кратчайшее. Для этого в реализации присутствует строчка if (u.first > dist[u.second]) continue;.

Заключение

Оказалось, что на самом деле очень легко писать Дейкстру за O(n * log(n) + m * log(n))!

Источник: https://codeforces.com/blog/entry/5558

Алгоритмы поиск в глубину и поиск в ширину — урок. Информатика, 11 класс

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

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

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

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

Рассмотрим несколько таких алгоритмов, которые можно составить.  

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

,, то следующая вершина выбирается смежной с вершиной  из числа невыбранных. Если для вершины такой вершины не нашлось, то возвращаемся к вершине −1 и для нее ищем смежную среди невыбранных. При необходимости возвращаемся назад и т.д.

Так будут перебраны все вершины графа и поиск закончится.

Пример:

На рисунках 1 и 2 показаны реализации поиска в глубину для одного и того же графа (начальная вершина — \(0\)).

 

Рис. 1

Рис. 2

Порядок  обхода графа с помощью алгоритма поиск в глубину для рисунка 1 — \(0, 1, 2, 3, 4, 5, 6, 9, 7, 10, 11, 8\), а для рисунка 2 — \(0, 1, 2, 4, 5, 3, 6, 7, 8, 9, 10, 11\). 

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

Если граф задан таблицей смежности, организуем одномерный массив \(В\), число элементов в котором совпадает с числом вершин в графе. На \(k-м\)  месте этого массива будем писать номер вершины, в которую мы попали на \(k-м\) шаге. Из всех смежных вершин будем выбирать вершину с наименьшим номером.

Алгоритм, реализующий поиск в глубину:

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

цел: \(k, m, s, t, u, n, a, v, i, G[1: n; 1: n], B[1: n]\);

{ Запросить \(n\);    (*запрашивается количество вершин*)

   Запросить G1:n;1:n;   (*реально это действие — ввод таблицы смежности — оформляется двойным циклом*)

   B1:=1;   (*в качестве исходной взята вершина с номером 1*)

   Делать от \(k := 2\)до \(n\)

  {  Bk:=0;

   }

   \(k := 1\);   (*счетчик количества пройденных вершин*)

   \(m := 0\);   (*k — m — порядковый номер вершины для очередного шага поиска*)

   Делать пока (\(k < n\))

   {  \(s := 1\);

      Делать от \(t := 1\)до \(n\)

      {  \(v := 1\);

         Делать от \(i := 1\)до \(k\)

         {  Если (Bi=t) то { \(v := 0\); } }

          Если ( \(v = 1\) иGBk−m,t=1) то

          { \(a := t\);

            \(s := 0\);

          }

}

(*если существует смежная вершина, которая еще не просматривалась, то \(s = 0\)*)

       Если (\(s = 0\)) то

       {  \(k := k + 1\);

           Bk:=a;

           \(m := 0\);

        }

        иначе  { \(m := m + 1\); }

     }

     Делать от \(k := 1\)до \(n\)

  { Сообщить Bk,k;

    }

}

Алгоритм поиск в ширину. Пусть зафиксирована начальная вершина v0. Рассматриваем все смежные с ней вершины v1,v2,…,. Затем рассматриваем смежные вершины каждой из рассмотренных вершин v1,v2,…,, и т.д. Так будут перебраны все вершины графа и поиск закончится.

Пример:

На рисунках 3 и 4 показаны реализации поиска в ширину для одного и того же графа (начальная вершина — \(0\)).

Рис. 3

Рис. 4

Порядок  обхода графа с помощью алгоритма поиск в ширину для рисунка 3 — \(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 1,0, 11\), а для рисунка 4 — \(0, 1, 2, 3, 4, 5, 6, 10, 7, 8, 9, 11, 12\).

Алгоритм, реализующий поиск в ширину:

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

цел: \(k, m, s, t, n, G[1: n; 1: n], B[1: n]\);

{ Запросить \(n\);    (*запрашивается количество вершин*)

   Запросить G1:n;1:n;   (*реально это действие — ввод таблицы смежности — оформляется двойным циклом*)

   B1:=1;   (*в качестве исходной взята вершина с номером 1*)

   Делать от \(k := 2\)до \(n\)

  {  Bk:=0;

   }

   \(s := 1\);

   Делать от \(k := 2\)до \(n\)

   {  \(t := 1\);     

       \(m := -1\);

       Делать пока (Gs,t=0 или\(t = s\) или Bt≠0)

      { \(t := t + 1\);

      }

      Если (\(t < n + 1\)) то

      {  Bt:=k;

          \(m := m + 1\);

       }

       иначе

       { \(s := k — m\);

        }

    }

    Делать от \(k := 1\)до \(n\)

  { Сообщить Bk,k;

    }

}

Источники:

Гейн А.Г., Сенокосов А.И. Информатика и ИКТ: учебник для общеобразовательных учреждений. — Москва: Просвещение, 2012. -227 с.

Источник: https://www.yaklass.ru/p/informatika/11-klass/grafy-i-algoritmy-na-grafakh-40408/algoritmy-obkhoda-sviaznogo-grafa-63116/re-294ff266-123b-4684-8764-8c529f60309c

Поиск в ширину (Breadth first search, BFS)

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

Обход означает посещение всех узлов графа.

«Обход в ширину» или «Поиск в ширину» (Breadth first traversal or Breadth first Search) — это рекурсивный алгоритм поиска всех вершин графа или древовидной структуры данных.

В этой статье вы познакомитесь с примерами алгоритма BFS, псевдокода BFS и кодом алгоритма «поиска в ширину» с реализацией в программах на C ++, C, Java и Python.

Алгоритм BFS

Стандартная реализация ВFS помещает каждую вершину графа в одну из двух категорий:

  1. Посещенные.
  2. Не посещенные.

Цель алгоритма — пометить каждую вершину, как посещенную, избегая циклов.

Алгоритм работает следующим образом:

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

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

Пример BFS

Давайте посмотрим, как алгоритм «поиска в ширину» работает на примере. Мы используем неориентированный граф с 5 вершинами.

Мы начнем с вершины 0, алгоритм BFS начинается с помещения его в список посещенных и размещения всех смежных вершин в стеке.

Затем мы посещаем элемент в начале очереди, то есть 1, и переходим к соседним узлам. Так как 0 уже был посещен, мы посещаем 2.

У вершины 2 есть соседняя не посещенная вершина 4, поэтому мы добавляем ее в конец очереди и посещаем 3, которая находится в начале очереди.

В очереди остается только 4, поскольку единственный соседний узел с 3, то есть 0, уже посещен. Мы посещаем вершину 4.

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

BFS псевдокод

create a queue Q mark v as visited and put v into Q while Q is non-empty remove the head u of Q mark and enqueue all (unvisited) neighbours of u

Код BFS

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

BFS в C

#include #include #define SIZE 40struct queue { int items[SIZE]; int front; int rear;};struct queue* createQueue();void enqueue(struct queue* q, int);int dequeue(struct queue* q);void display(struct queue* q);int isEmpty(struct queue* q);void printQueue(struct queue* q);struct node{ int vertex; struct node* next;};struct node* createNode(int);struct Graph{ int numVertices; struct node** adjLists; int* visited;};struct Graph* createGraph(int vertices);void addEdge(struct Graph* graph, int src, int dest);void printGraph(struct Graph* graph);void bfs(struct Graph* graph, int startVertex);int main(){ struct Graph* graph = createGraph(6); addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 1, 2); addEdge(graph, 1, 4); addEdge(graph, 1, 3); addEdge(graph, 2, 4); addEdge(graph, 3, 4); bfs(graph, 0); return 0;}void bfs(struct Graph* graph, int startVertex) { struct queue* q = createQueue(); graph->visited[startVertex] = 1; enqueue(q, startVertex); while(!isEmpty(q)){ printQueue(q); int currentVertex = dequeue(q); printf(«Visited %d», currentVertex); struct node* temp = graph->adjLists[currentVertex]; while(temp) { int adjVertex = temp->vertex; if(graph->visited[adjVertex] == 0){ graph->visited[adjVertex] = 1; enqueue(q, adjVertex); } temp = temp->next; } }} struct node* createNode(int v){ struct node* newNode = malloc(sizeof(struct node)); newNode->vertex = v; newNode->next = NULL; return newNode;} struct Graph* createGraph(int vertices){ struct Graph* graph = malloc(sizeof(struct Graph)); graph->numVertices = vertices; graph->adjLists = malloc(vertices * sizeof(struct node*)); graph->visited = malloc(vertices * sizeof(int)); int i; for (i = 0; i < vertices; i++) { graph->adjLists[i] = NULL; graph->visited[i] = 0; } return graph;} void addEdge(struct Graph* graph, int src, int dest){ // Add edge from src to dest struct node* newNode = createNode(dest); newNode->next = graph->adjLists[src]; graph->adjLists[src] = newNode; // Add edge from dest to src newNode = createNode(src); newNode->next = graph->adjLists[dest]; graph->adjLists[dest] = newNode;}struct queue* createQueue() { struct queue* q = malloc(sizeof(struct queue)); q->front = -1; q->rear = -1; return q;}int isEmpty(struct queue* q) { if(q->rear == -1) return 1; else return 0;}void enqueue(struct queue* q, int value){ if(q->rear == SIZE-1) printf(«Queue is Full!!»); else { if(q->front == -1) q->front = 0; q->rear++; q->items[q->rear] = value; }}int dequeue(struct queue* q){ int item; if(isEmpty(q)){ printf(«Queue is empty»); item = -1; } else{ item = q->items[q->front]; q->front++; if(q->front > q->rear){ printf(«Resetting queue»); q->front = q->rear = -1; } } return item;}void printQueue(struct queue *q) { int i = q->front; if(isEmpty(q)) { printf(«Queue is empty»); } else { printf(«Queue contains «); for(i = q->front; i < q->rear + 1; i++) { printf(«%d «, q->items[i]); } } }

BFS в C++

#include #include using namespace std; class Graph{ int numVertices; list *adjLists; bool* visited;public: Graph(int vertices); void addEdge(int src, int dest); void BFS(int startVertex);}; Graph::Graph(int vertices){ numVertices = vertices; adjLists = new list[vertices];} void Graph::addEdge(int src, int dest){ adjLists[src].push_back(dest); adjLists[dest].push_back(src);} void Graph::BFS(int startVertex){ visited = new bool[numVertices]; for(int i = 0; i < numVertices; i++) visited[i] = false; list queue; visited[startVertex] = true; queue.push_back(startVertex); list::iterator i; while(!queue.empty()) { int currVertex = queue.front(); cout

Источник: https://evileg.com/ru/post/512/

Графы. Поиск в ширину и глубину на Prolog

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

В статье описываются:

  • алгоритмы обхода графа в глубину и в ширину;
  • представление графов на языке Prolog;
  • реализация алгоритмов обхода графа на языке Prolog.

1 Графы. Обходы графа

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

Кроме того, нередко встает задача поиска кратчайших путей. Во взвешенном графе (ребра графа имеют определенный вес) кратчайший путь имеет наименьшую сумму весов входящих в него ребер. Для поиска такого пути есть специальные алгоритмы (такие как Беллмана-Форда), но они не рассматриваются в этой статье [3, 4].

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

В примерах статьи, поиск путей производится на графе, изображенном на рис. 1.

рис. 1 пример графа

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

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

1. начало; функция breadth(G, Start, Finish) ; обход графа в ширину ; G — граф, ; Finish — начальная вершина, ; Start — конечная вершина 2. пометить вершину Start как обработанную; 3.

выбрать дугу (Start, X), такую, что вершина X не обработана, если дуги нет — переход на п.4; 3.1. если в G есть дуга (Start, Finish) — вернуть (true, (Start, Finish)); 3.2. (Res, Path) := breadth(G, X, Finish); 3.3.

если Res = true — вернуть (true, (Start, X) + Path); 3.4. вернуть breadth(G, Start, Finish); 4. конец — вернуть (false, ()).

В результате рекурсивного вызова (п. 3.2) может быть найден путь, проходящий через одну из смежных со Start дуг. Если путь найден — то его необходимо дополнить соответствующей дугой (п.3.3), в противном случае — перейти к поиску пути, проходящему через другую дугу (п. 3.4).

Стоит отметить, что на шаге 3 алгоритма листинг 1 выбирается произвольная дуга, однако, выбор дуга влияет на результат, т.к. алгоритм не гарантирует что найденный путь будет кратчайшим.

Например, если при поиске пути из вершины P а вершину F, первой будет выбрана дуга (P, D), то будет найден путь (P, D, F), однако, если первой будет взята дуга (P, B), то может быть найден путь (P, B, C, D, F).

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

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

На рис. 2 цветом показан порядок обработки вершин при поиске пути из узла B. Черным цветом выделены вершины, не достижимые из стартовой. Пунктирная линия изображает возможную альтернативу (вершина F может быть добавлена с использованием дуги (D, F) или дуги (E, F)).

рис. 2 обход графа в ширину

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

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

1. начало; функция breadth(G, Queue_add, Queue_proc, Finish, Res) ; обход графа в ширину ; G — граф, ; Queue_add — очередь добавленных вершин (не обработанных) ; Queue_proc — очередь обработанных вершин ; Finish — конечная вершина ; Res — список использованных дуг 2. если Queue пуст — вернуть (false, Res); 3. получить H узел из начала Queue_add; 4.

если H = Finish — вернуть (true, Res); 5. adj_nodes := список вершин, смежных с H; 6. удалить из adj_nodes вершины, присутствующие в Queue_add или Queue_proc; 7. удалить H из Queue_add, добавить H в Queue_proc; 8. добавить в конец Queue_add вершины из adj_nodes; 9. добавить в Res дуги между узлом H и вершинами из adj_nodes; 10.

вернуть breadth(G, Queue_add, Queue_proc, Finish, Res); 11. конец.

По алгоритму листинг 2, поиск продолжается пока не будут обработаны все доступные вершины (п. 2), либо не будет найдена нужная вершина (п.4). Функция breadth выбирает вершину из начала очереди обработки (п.3), и добавляет новые в конец (п.

8) — за счет этого обеспечивается требуемый порядок обхода — чем более узел удален от стартовой вершины — тем позже он будет обработан.

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

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

1. начало; функция path(Start, Finish, Edges) ; восстановление пути между двумя вершинами по дугам ; Start — начало пути ; Finish — конец пути ; Edges — дуги, полученные поиском в ширину 2.

если в Edges нет дуги (Start, Finish) — переход к п.3; 2.1. вернуть список из одной дуги (Start, Finish); 3. получить дугу (X, Finish) из Edges; 4. PartPath := path(Start, X, Edges) 5.

PartPath := (X, Finish) + PartPath; 6. конец (вернуть PartPath).

Если алгоритм поиска в ширину (функция breadth) вернул true — то соответствующий набор дуг гарантированно содержит искомый путь и функция path в п.3 найдет дугу, принадлежащую этому пути.

2 Обход графа в ширину и глубину на языке Prolog

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

В базе удобно хранить информацию об узлах (node) и дугах (edge). Граф рис. 1 мог бы быть описан следующими фактами:

/* nodes */ node(a). node(b). node(c). node(d). node(e). node(f). node(g). node(h). node(k). node(m). node(p). node(s). /* edges */ edge(a, b). edge(a, c). edge(a, g). edge(b, a). edge(b, c). edge(c, e). edge(c, d). edge(d, f). edge(e, g). edge(e, f). edge(e, h). edge(f, k). edge(g, c). edge(g, e). edge(m, d). edge(p, b). edge(p, d).

2.1 Реализация алгоритма поиска в глубину на Prolog

dfs(From, To, _, [edge(From, To)]):- edge(From, To). dfs(From, To, VisitedNodes, [(From, X)|TailPath]):- edge(From, X), not(member(X, VisitedNodes)), dfs(X, To, [From|VisitedNodes], TailPath).

Первые 2 строки соответствуют пункту 3.1 алгоритма листинг 1, четвертая строка — пункту 3.2, третья и пятая — 3.3. В случае если пути между заданными вершинами нет — правило завершается неудачей (вместо флага результата).

рис. 3 пример поиска в глубину на Prolog

Вызовы правила dfs на рис.3 проводились для графа рис. 1. Как видно, описанный предикат позволяет найти все пути из начальной вершины в конечную. В связи с этим, если нужен кратчайший путь и не важна оптимальность работы алгоритма — можно найти все пути и выбрать кратчайший.

2.2 Реализация алгоритма поиска в ширину на Prolog

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

/* path\3 возвращает путь @3 из вершины @1 в вершину @2 */ path(A, B, Path):- breadth([A], [], [], B, UE), path(A, B, UE, Path).

Правило восстановления пути (path\4) соответствует алгоритму листинг 3.

/* path\4 восстанавливает путь @4 из вершины @1 в вершину @2 по дугам @3 */ path(A, B, UE, [(A, B)]):- member((A, B), UE), !. path(A, B, UE, Path):- member((X, B), UE), !, path(A, X, UE, TPath), append(TPath, [(X, B)], Path).

Обход графа в ширину реализуется правилом breadth\5 в соответствии с листинг 2, при этом, реализация пунктов 5 и 6 (добавления и фильтрация смежных вершин выполняется правилом add_adj\6.

/* breadth обход графа в ширину @1 список добавленных вершин @2 исходный список использованных дуг @3 список пройденных вершин @4 конечная вершина @5 результат — список использованных дуг */ breadth([], _, _, _, _):-!, fail. breadth([H|_], UE, _, H, UE):-!. breadth(V, UE, UV, FV, RUE):- add_adj(V, UE, UV, TV, TUE, TUV), breadth(TV, TUE, TUV, FV, RUE).

Правило add_adj\6 использует adj_filter\4 для реализации п.6 алгоритма, и add_adj_edges\4 — для реализации п.7.

/* adj_filter\4 удаляет из списка вершин @1, вершины, входящие в @2 или @3. Результат в @4 */ adj_filter([], _, _, []):-!. adj_filter([H|T], L1, L2, [H|TR]):- not(member(H, L1)), not(member(H, L2)), !, adj_filter(T, L1, L2, TR). adj_filter([_|T], L1, L2, TR):- adj_filter(T, L1, L2, TR).

/* add_adj_edges добавляет дуги из вершины @1 до вершин списка @2 в список @3. Результат в @4 */ add_adj_edges(_, [], R, R):-!. add_adj_edges(SV, [H|T], IL, [(SV,H)|TR]):- add_adj_edges(SV, T, IL, TR).

/* add_adj/6 @1 исходный список добавленных вершин @2 исходный список дуг @3 исходный список пройденных вершин @4 результат — список добавленных вершин @5 результат — список дуг @6 результат — список пройденных вершин */ add_adj([], _, _, _, _, _):-!, fail.

add_adj([H|T], UE, UV, RV, RUE, RUV):- findall(X, edge(H, X), AVHL), % получили список смежных вершин adj_filter(AVHL, UE, UV, FAVHL), % убрали из него лишние вершины append(T, FAVHL, RV), % изменив порядок соединения списков, % можно получить обход в глубину add_adj_edges(H, FAVHL, UE, RUE), RUV = [H|UV], !.

рис. 4 пример поиска в ширину

Исходный код алгоритма поиска в ширину можно скачать. При реализации использовался SWI Prolog, однако, код писался так, чтобы его без особых усилий можно было запустить Visual Prolog 5.2.

Список использованных источников

  1. Валетов В.А., Орлова А.А., Третьяков С.Д. Интеллектуальные технологии производства приборов и систем. Учебное пособие, — СПб: СПб ГУИТМО, 2008. – 134 с.
  2. Афонин В.Л., Макушкин В.А. Интеллектуальные робототехнические системы, Интернет-университет информационных технологий, 2005
  3. Макоха А.Н., Сахнюк П.А., Червяков Н.И. — Дискретная математика. Учеб. пособие (ФМЛ, 2005)
  4. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики. Учебник. М.: ИНФРА-М, Новосибирск: Изд-во НГТУ, 2002
  5. Книги раздела «Алгоритмы»
  6. Вариант реализации поиска в ширину на невзвешенном графе.

Источник: https://pro-prof.com/archives/1283

Графы. Обход графов в ширину и глубину

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

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

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

Примеры графов разных типов:

обычный

ориентированный

взвешенный

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

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

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

A

B

C

D

E

A

0

1

1

1

1

B

1

0

0

0

1

C

1

0

0

1

0

D

1

0

1

0

0

E

1

1

0

0

0

A

B

C

D

E

A

0

1

1

0

0

B

1

0

0

0

1

C

0

1

0

1

1

D

1

0

0

0

1

E

0

0

0

0

0

A

B

C

D

E

A

0

15

0

9

0

B

15

0

10

0

0

C

0

10

0

22

6

D

9

0

22

0

19

E

0

0

6

19

0

Недостатки данного способа:

  • заранее надо знать хотя бы ориентировочное число вершин в графе
  • для графов с большим числом вершин матрица становится слишком большой (например 1000*1000 = 1 миллион чисел)
  • при малом числе связующих ребер матрица заполнена в основном нулями

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

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

Для рассмотренных выше обычного графа и ориентированного графа списки смежности будут следующими:

  Описание подобной сложной списковой структуры выполняется обычным образом.

Операции добавления и удаления по сравнению с деревьями имеют следующие варианты:

  • добавление новой связи (ребра) между заданной парой существующих вершин
  • добавление новой вершины вместе со всеми необходимыми связями
  • удаление связи (ребра) между двумя вершинами
  • удаление вершины вместе со всеми ее связями

Добавление нового ребра включает в себя (на примере обычного графа):

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

Добавление новой вершины включает в себя:

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

Удаление ребра производится следующим образом:

  • запрос имен двух вершин, между которыми разрывается связь
  • поиск в основном списке каждой из этих вершин
  • поиск в каждом из двух вспомогательных списков имени соседней вершины и удаление соответствующего элемента

Удаление вершины производится следующим образом:

  • запрос имени удаляемой вершины
  • поиск ее в основном списке
  • просмотр вспомогательного списка удаляемой вершины, для каждого элемента которого:
    • поиск смежной вершины в основном списке и удаление из ее вспомогательного списка элемента, соответствующего удаляемой вершине
    • удаление самого элемента из вспомогательного списка
  • удаление вершины из основного списка

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

Обход в глубину

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

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

Например, для рассмотренного выше обычного графа получим:

      • пусть стартовая вершина – B
      • включаем B в список обработанных вершин: список = (В)
      • помещаем в стек смежные с В вершины, т.е. A и E: стек = (А, Е)
      • извлекаем из стека вершину E: стек = (А)
      • т.к. E нет в списке обработанных вершин, то обрабатываем ее и помещаем в список: список = (В, Е)
      • смежные с E вершины – это A и B, но B уже обработана, поэтому помещаем в стек только вершину А: стек = (А, А)
      • извлекаем из стека вершину А: стек = (А)
      • т.к. А нет в списке обработанных вершин, то помещаем ее туда: список = (В, Е, А)
      • смежные с А вершины – это B, C, D, E, из которых B и E уже обработаны, поэтому помещаем в стек C и D: стек = (A, C, D)
      • извлекаем из стека вершину D: стек = (A, C)
      • т.к. D не обработана, то помещаем ее в список: список = (B, E, A, D)
      • смежные с D вершины – это А и С, из которых А уже обработана, поэтому помещаем в стек вершину С: стек = (А, С, С)
      • извлекаем из стека вершину С: стек = (А, С)
      • т.к. С не обработана, помещаем ее в список: список = (B, E, A, D, C)
      • смежные с С вершины – это A и D, но они обе уже обработаны, поэтому в стек ничего не заносим
      • извлекаем из стека С, но она уже обработана
      • извлекаем из стека А, но она тоже уже обработана
      • т.к. стек стал пустым, то завершаем обход с результатом (B, E, A, D, C)

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

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

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

Тот же что и раньше пример даст следующий результат:

      • пусть стартовая вершина – B
      • включаем B в список обработанных вершин: список = (В)
      • помещаем в очередь смежные с В вершины, т.е. A и E: очередь = (А, Е)
      • извлекаем из очереди вершину А: очередь = (Е)
      • т.к. она не обработана, добавляем ее в список: список = (В, А)
      • смежные с А вершины – это B, C, D и E, помещаем в очередь вершины C, D и E: очередь = (E, C, D, E)
      • извлекаем из очереди вершину Е: очередь = (C, D, E)
      • т.к. Е не обработана, помещаем ее в список: список = (B, A, E), т.е. в первую очередь обработаны обе смежные с В вершины
      • смежные с Е вершины – это А и В, но обе они уже обработаны, поэтому очередь новыми вершинами не пополняется
      • извлекаем из очереди вершину С: очередь = (D, E)
      • т.к. С не обработана, то помещаем ее в список: список = (B, A, E, С)
      • смежные с С вершины – это А и D, помещаем в очередь только D: очередь = (D, E, D)
      • извлекаем из очереди вершину D: очередь = (E, D)
      • т.к. D не обработана, помещаем ее в список: список = (B, A, E, С, D)
      • смежные с D вершины – это А и С, но обе они обработаны, поэтому очередь не пополняется
      • извлекаем из очереди вершину Е, но она уже обработана: очередь = (D)
      • извлекаем из очереди вершину D, но она уже обработана и т.к. очередь становится пустой, то поиск заканчивается с результатом (B, A, E, С, D), что отличается от поиска в глубину.

В заключение отметим несколько наиболее часто встречающихся задач на графах:

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

Источник: https://shpargalum.ru/shpora-gos-povtas/strukturyi-i-algoritmyi-obrabotki-dannyix/grafyi.-obxod-grafov-v-shirinu-i-glubinu.html

Booksm
Добавить комментарий