Поиск в ширину (Breadth first search, BFS). Обход графа в ширину.

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

Поиск, обход в глубину и ширину в графе: алгоритм, описание

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

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

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

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

Задачи для обхода графа вширь или вглубь могут быть следующими:

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

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

Breadth First Search (BSD) сначала рассматривает все вершины, смежные с исходной вершиной, а затем переходит к их потомкам. Он характеризуется беспрепятственным движением «от соседа к соседу», где один шаг — это посещение «соседа». При его выполнении формируется очередь узлов, которые еще не были пройдены. Этот алгоритм выполняется до тех пор, пока не будет найдено искомое значение.

Поиск диапазона выполняется в следующей последовательности действий:

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

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

Поиск в глубину или DFS (Depth First Search) дает представление о таком поиске, где мы указываем начальный узел и направление движения. Поиск следует в этом направлении до конца пути или пока не будет найдено желаемое пиковое значение. Если в конце пути значение не найдено, поиск возвращается «назад» к ближайшей точке отклонения и выбирается новое направление для пути глубины.

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

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

При поиске в глубину выполняется следующая последовательность действий:

1. Задается стартовая вершина.
2. Определяется искомое значение.
3. Задается вероятный путь для поиска нужного значения.
4. Если в процессе прохождения пути цель была достигнута, то поиск в глубину считается завершенным. Если же нет, то поиск происходит по новому пути, при этом новый путь выбирается с учетом уже посещенных вершин.

Алгоритм поиска в глубину характеризуется движением к концу пути.

Пример BFS

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

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

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

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

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

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

BFS в C

#include #define SIZE 40 struct queuestruct 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 nodestruct node* createNode(int); struct Graphstruct 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()void bfs(struct Graph* graph, int startVertex)enqueue(q, startVertex) = 1; while(!isEmpty(q))adjListscurrentVertex; while(temp)vertex; if(graph->(temp); while(temp == 0)visitedadjVertex = 1; enqueue(q, adjVertex);>temp = temp->next;>>>struct node* createNode(int v)vertex = v; newNode->next = NULL; return newNode;>struct Graph* createGraph(int vertices)numVertices = vertices; graph->adjLists = malloc(vertices * sizeof(struct node*)); graph->visited = malloc(vertices * sizeof(int)); int i; for (i = 0; iadjListsi = NULL; graph->visitedi = 0;>return graph;>void addEdge(struct Graph* graph, int src, int dest)next = graph->adjListssrc; graph->adjListssrc = newNode; // Add edge from dest to src newNode = createNode(src); newNode->next = graph->adjListsdest; graph->adjListsdest = newNode;>struct queue* createQueue()front = -1; q->rear = -1; return q;>int isEmpty(struct queue* q)rear == -1) return 1; else return 0;>void enqueue(struct queue* q, int value)rear == SIZE-1) printf("front == -1) q->front = 0; q->rear++; q->itemsq->rear = value;>>Queue is Full!!!"); elseint dequeue(struct queue* q)itemsq->front; q->front++; if(q->front>q->иначеfront = q->rear = -1;>>return item;>назад)void printQueue(struct queue *q)front; if(isEmpty(q))elseфронт; iitemsi);>>>
back + 1; i++)#include #include using namespace std; class Graph; Graph::Graph(int vertices)void Graph::addEdge(int src, int dest)BFS Java код (Java code)
void Graph::BFS(int startVertex)>>>import java.io.*; import java.util.*; class Graph>
public static void main(String args)

import collections def bfs(graph, root): visited, queue = set(), collections.deque(root) visited.add(root) while queue: vertex = queue.popleft() for neighbour in graphvertex: 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 вопросов
Обход в ширину (breadth-first search, BFS)
Вопрос. Все, что мы видели раньше, только в коде. G.Adj - список смежности данного графа. Для каждой вершины, которая еще не была посещена, мы окрашиваем ее в серый цвет, указывая, что ее поле истинно; таким образом мы проходим через все вершины. Почему мы вызываем dfs для каждой вершины в init()? Мы не можем начать с первой вершины, потому что в приведенном выше графе dfs немедленно закончится, если мы начнем с вершины 3, поскольку из нее нет исходящих дуг.
Он систематически обходит все узлы графа. В чем разница с обходом по глубине? Обход в глубину "прыгает" между строками списка смежности по одному узлу за раз, в то время как обход в ширину обходит все возможные узлы сразу, как это работает в примере:
Сначала обходятся все узлы, соседние с исходным узлом, затем все узлы, соседние с исходным узлом, и так далее. Вот еще один пример, который, на мой взгляд, более наглядно демонстрирует разницу между обходами в глубину и ширину: В первом примере граф обходится достаточно равномерно.

Упорядочивание BFS
Псевдокод с краткими пояснениями:
Пусть G = (V, E) будет графиком с n вершин. Напомним, что N (v) - это набор соседей v. Для σ = (v 1,…, vm), \ dots, v_ )>быть списком отдельных элементов V, для v ∈ V ∖, \ dots, v_ \>>, пусть ν σ (v) (v)>Перечисление вершин в графе называется массивом BFS, если оно является возможным результатом применения BFS к этому графу.<\ displaystyle i>такой, что vi>Возможный результат BFS - это возможный результат гипотезы, которая является результатом возможного решения графа в BFS
Пусть σ = (v 1,…, vn), \ dots, v_ )>будет перечислением вершин V. Перечисление σ называется упорядочением BFS (с источником v 1>), если, для всех 1, vi>- это вершина w ∈ V ∖, \ dots, v_ \>>такие, что ν (v 1,…, vi - 1) (w), \ dots, v_ )>(w)>минимально. Эквивалентно, σ является порядком BFS, если для всех 1 ≤ i с vi ∈ N (vk) ∖ N (vj) \ in N (v_ ) \ setminus N (v_ )>, существует сосед vm>быть соседом v, если такой i существует, и в противном случае быть ∞.<\ displaystyle v_>из vj
Applications
такой, что m .

Копирование сборки мусора, алгоритм Чейни
Поиск кратчайшего пути между двумя узлами u и v, длина пути измеряется количество ребер (преимущество перед поиском в глубину )
(обратный) Cuthill – McKee нумерация сетки
метод Форда – Фулкерсона для вычисления максимального потока в потоковая сеть
Сериализация / десериализация двоичного дерева по сравнению с сериализацией в отсортированном порядке, позволяет эффективно реконструировать дерево.
Построение функции отказа Ахо-Ко rasick сопоставление с образцом.
Проверка двудольности графа.