Изменения
Нет описания правки
'''Поиск Обход в ширину''' ('''Поиск в ширину, BFS''', Breadth-first search) — один из простейших алгоритмов обхода графа, являющийся основой для многих важных алгоритмов для работы с графами. Например, алгоритм [[Алгоритм Прима|Прима]] поиска минимального остовного дерева или алгоритм [[Алгоритм Дейкстры|Дейкстры]] поиска кротчайшего пути из одной вершины используют идеи, сходные идеямиидеям, используемыми используемым при поиске в ширину.
==Алгоритм==
Для отслеживания работы алгоритма поиск в ширину раскрашивает вершины графа в белый, серый и черный цвета. Изначально все вершины белые, и позже они могут стать серыми, а затем черными. Когда вершина '''открывается''' в процессе поиска, она окрашивается. Таким образом, серые и черные вершины — это вершины, которые уже были открыты, но алгоритм поиска в ширину по-разному работает с ними, чтобы обеспечить объявленный порядок обхода. Если <tex>(u, v) \in E</tex> и вершина <tex>u</tex> черного цвета, то вершина <tex>v</tex> либо серая, либо черная, т.е. все вершины, смежные с ней уже открыты. Серые вершины могут иметь белых соседей, представляя собой границу между открытыми и неоткрытыми вершинами.
Поиск в ширину стоит дерево поиска в ширину, которое изначально состоит из одного корня, которым является исходная вершина <tex>s</tex>. Если в процессе сканирования списка смежности уже открытое вершины <tex>u</tex> открывается белая вершина <tex>v</tex>, то вершина <tex>v</tex> и ребро <tex>(u, v)</tex> добавляются в дерево. При этом <tex>u</tex> является '''предшественником''' (predecessor), или '''родителем''' (parent), <tex>v</tex> в дереве поиска вширьвширину. Посколько вершина модет быть открыта не более одного раза, она имеет не более одного родителя.
=== Реализация===
