Что такое bfs

Обход в ширину

Обход в ширину (Поиск в ширину, англ. BFS, Breadth-first search) — один из простейших алгоритмов обхода графа, являющийся основой для многих важных алгоритмов для работы с графами.

Описание алгоритма

Алгоритм BFS
посещенные вершины

Пусть задан невзвешенный ориентированный граф [math] G = (V, E) [/math] , в котором выделена исходная вершина [math]s[/math] . Требуется найти длину кратчайшего пути (если таковой имеется) от одной заданной вершины до другой. Частным случаем указанного графа является невзвешенный неориентированный граф, т.е. граф, в котором для каждого ребра найдется обратное, соединяющее те же вершины в другом направлении.

Для алгоритма нам потребуются очередь и множество посещенных вершин [math] was [/math] , которые изначально содержат одну вершину [math] s [/math] . На каждом шагу алгоритм берет из начала очереди вершину [math] v [/math] и добавляет все непосещенные смежные с [math] v [/math] вершины в [math] was [/math] и в конец очереди. Если очередь пуста, то алгоритм завершает работу.

Анализ времени работы

Оценим время работы для входного графа [math]G = (V, E)[/math] , где множество ребер [math] E [/math] представлено списком смежности. В очередь добавляются только непосещенные вершины, поэтому каждая вершина посещается не более одного раза. Операции внесения в очередь и удаления из нее требуют [math] O(1) [/math] времени, так что общее время работы с очередью составляет [math] O(|V|) [/math] операций. Для каждой вершины [math] v [/math] рассматривается не более [math] \mathrm(v) [/math] ребер, инцидентных ей. Так как [math] \sum\limits_ \mathrm(v) = 2|E| [/math] , то время, используемое на работу с ребрами, составляет [math] O(|E|) [/math] . Поэтому общее время работы алгоритма поиска в ширину — [math] O(|V| + |E|) [/math] .

Корректность

В очереди поиска в ширину расстояние вершин до [math]s[/math] монотонно неубывает.

Докажем это утверждение индукцией по числу выполненных алгоритмом шагов.

Введем дополнительный инвариант: у любых двух вершин из очереди, расстояние до [math] s [/math] отличается не более чем на [math] 1 [/math] .

База: изначально очередь содержит только одну вершину [math] s [/math] .

Переход: пусть после [math] i-й [/math] итерации в очереди [math] a + 1 [/math] вершин с расстоянием [math] x [/math] и [math] b [/math] вершин с расстоянием [math] x + 1 [/math] .

Рассмотрим [math] i-ю [/math] итерацию. Из очереди достаем вершину [math] v [/math] , с расстоянием [math] x [/math] . Пусть у [math]v[/math] есть [math]r [/math] непосещенных смежных вершин. Тогда, после их добавления, в очереди находится [math] a [/math] вершин с расстоянием [math] x [/math] и, после них, [math] b + r [/math] вершин с расстоянием [math] x + 1 [/math] .

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

Допустим, что это не так. Выберем из вершин, для которых кратчайшие пути от [math] s [/math] найдены некорректно, ту, настоящее расстояние до которой минимально. Пусть это вершина [math] u [/math] , и она имеет своим предком в дереве обхода в ширину [math] v [/math] , а предок в кратчайшем пути до [math] u [/math] — вершина [math] w [/math] .

Так как [math] w [/math] — предок [math] u [/math] в кратчайшем пути, то [math] \rho(s, u) = \rho(s, w) + 1 \gt \rho(s, w) [/math] , и расстояние до [math] w [/math] найдено верно, [math] \rho(s, w) = d[w] [/math] . Значит, [math] \rho(s, u) = d[w] + 1 [/math] .

Так как [math] v [/math] — предок [math] u [/math] в дереве обхода в ширину, то [math] d[u] = d[v] + 1 [/math] .

Дерево обхода в ширину

Поиск в ширину также может построить дерево поиска в ширину. Изначально оно состоит из одного корня [math] s [/math] . Когда мы добавляем непосещенную вершину в очередь, то добавляем ее и ребро, по которому мы до нее дошли, в дерево. Поскольку каждая вершина может быть посещена не более одного раза, она имеет не более одного родителя. После окончания работы алгоритма для каждой достижимой из [math] s [/math] вершины [math] t [/math] путь в дереве поиска в ширину соответствует кратчайшему пути от [math] s [/math] до [math] t [/math] в [math] G [/math] .

Реализация

Предложенная ниже функция возвращает кратчайшее расстояние между двумя вершинами.

• [math] \mathtt [/math] — исходная вершина
• [math] \mathtt [/math] — конечная вершина
• [math] \mathtt [/math] — граф, состоящий из списка вершин [math] \mathtt [/math] и списка смежности [math] \mathtt [/math] . Вершины нумеруются целыми числами.
• [math] \mathtt [/math] — очередь.
• В поле [math] \mathtt [/math] хранится расстояние от [math] \mathtt [/math] до [math] \mathtt [/math] .

int BFS(G: (V, E), source: int, destination: int): d = int[|V|] fill(d, [math] \infty [/math]) d[source] = 0 Q = [math] \varnothing [/math] Q.push(source) while Q [math] \ne \varnothing [/math] u = Q.pop() for v: (u, v) in E if d[v] == [math] \infty [/math] d[v] = d[u] + 1 Q.push(v) return d[destination]

Если требуется найти расстояние лишь между двумя вершинами, из функции можно выйти, как только будет установлено значение [math] \mathtt [/math] . Еще одна оптимизация может быть проведена при помощи метода meet-in-the-middle.

Вариации алгоритма

0-1 BFS

Пусть в графе разрешены ребра веса [math] 0 [/math] и [math] 1 [/math] , необходимо найти кратчайший путь между двумя вершинами. Для решения данной задачи модифицируем приведенный выше алгоритм следующим образом:

Вместо очереди будем использовать дек (или можно даже steque). Если рассматриваемое ее ребро имеет вес [math] 0 [/math] , то будем добавлять вершину в начало, а иначе в конец. После этого добавления, дополнительный введенный инвариант в доказательстве расположения элементов в деке в порядке неубывания продолжает выполняться, поэтому порядок в деке сохраняется. И, соответственно, релаксируем расстояние до всех смежных вершин и, при успешной релаксации, добавляем их в дек.

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

1-k BFS

Пусть в графе разрешены ребра целочисленного веса из отрезка [math]1 \ldots k[/math] , необходимо найти кратчайший путь между двумя вершинами. Представим ребро [math]uv[/math] веса [math]m[/math] как последовательность ребер [math]uu_1u_2 \ldots u_v[/math] (где [math]u_1 \ldots u_[/math] — новые вершины). Применим данную операцию ко всем ребрам графа [math] G [/math] . Получим граф, состоящий (в худшем случае) из [math]k|E|[/math] ребер и [math]|V| + (k — 1)|E|[/math] вершин. Для нахождения кратчайшего пути следует запустить BFS на новом графе. Данный алгоритм будет иметь асимптотику [math] O(|V| + k|E|) [/math] .

См. также

• Обход в глубину, цвета вершин
• Алгоритм Дейкстры
• Теория графов

Источники информации

• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4
• MAXimal :: algo :: Поиск в ширину
• Wikipedia — Breadth-first search
• Wikipedia — Поиск в ширину
• Визуализатор алгоритма

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

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

Обход означает посещение всех узлов графа. «Обход в ширину» или «Поиск в ширину» (Breadth first traversal or Breadth first Search) — это рекурсивный алгоритм поиска всех вершин графа или древовидной структуры данных. В этой статье вы познакомитесь с примерами алгоритма BFS, псевдокода BFS и кодом алгоритма «поиска в ширину» с реализацией в программах на C ++, C, Java и Python.

Алгоритм BFS

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 40 struct 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\n", 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("\nQueue 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("\nQueue contains \n"); 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 > > > int main()
BFS Java код (Java code)
import java.io.*; import java.util.*; class Graph < private int numVertices; private LinkedListadjLists[]; private boolean visited[]; Graph(int v) < numVertices = v; visited = new boolean[numVertices]; adjLists = new LinkedList[numVertices]; for (int i=0; i i = adjLists[currVertex].listIterator(); while (i.hasNext()) < int adjVertex = i.next(); if (!visited[adjVertex]) < visited[adjVertex] = true; queue.add(adjVertex); >> > > public static void main(String args[]) < Graph g = new Graph(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); System.out.println("Following is Breadth First Traversal "+ "(starting from vertex 2)"); g.BFS(2); >>
BFS в Python
import collections def bfs(graph, root): visited, queue = set(), collections.deque([root]) visited.add(root) while queue: vertex = queue.popleft() for neighbour in graph[vertex]: if neighbour not in visited: visited.add(neighbour) queue.append(neighbour) if __name__ == '__main__': graph = breadth_first_search(graph, 0)

Рекомендуем хостинг TIMEWEB
Стабильный хостинг, на котором располагается социальная сеть EVILEG. Для проектов на Django рекомендуем VDS хостинг.
Рекомендуемые статьи по этой тематике







Алгоритм Прима
Алгоритм Краскала
Алгоритм DFS («Depth-first search» или «Поиск в глубину»)
Граф. Структура данных.
Двоичное дерево поиска (Binary Search Tree (BST))
Обход дерева – центрированный (inorder), прямой (preorder) и обратный (postorder) (три основных способа обхода)

По статье задано0 вопрос(ов) 
Подписка на обсуждение 4

Подписка на раздел 78
Вам это нравится? Поделитесь в социальных сетях!
Поиск в ширину
Поиск в ширину (англ. breadth-first search) — один из основных алгоритмов на графах, позволяющий находить все кратчайшие пути от заданной вершины и решать многие другие задачи.
Поиск в ширину также называют обходом — так же, как поиск в глубину и все другие обходы, он посещает все вершины графа по одному разу, только в другом порядке: по увеличению расстояния до начальной вершины.






#Описание алгоритма
На вход алгоритма подаётся невзвешенный граф и номер стартовой вершины $s$. Граф может быть как ориентированным, так и неориентированным — для алгоритма это не важно.
Основную идею алгоритма можно понимать как процесс «поджигания» графа: на нулевом шаге мы поджигаем вершину $s$, а на каждом следующем шаге огонь с каждой уже горящей вершины перекидывается на всех её соседей, в конечном счете поджигая весь граф.
Если моделировать этот процесс, то за каждую итерацию алгоритма будет происходить расширение «кольца огня» в ширину на единицу. Номер шага, на котором вершина $v$ начинает гореть, в точности равен длине её минимального пути из вершины $s$.
 

Обратим внимание, что путь выведется в обратном порядке.

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

  Сложность такого алгоритма будет $O(k n + m)$, поскольку каждую вершину мы можем прорелаксировать и добавить в другую очередь не более $k$ раз, а просматривать рёбра, исходящие из вершины мы будем только когда обработаем эту вершину в самый первый раз.