Изменения
→Общая идея
===Общая идея===
Пусть задан граф <tex>G = (V, E)</tex> и выделена исходная вершина <tex>s</tex>. Алгоритм поиска в ширину систематически обходит все ребра <tex>G</tex> для "открытия" всех першинвершин, достижимых из <tex>s</tex>, вычисляя при этом расстояние (минимальное количество ребер) от <tex>s</tex> до каждой достижимой из <tex>s</tex> вершины. Кроме того, в процессе обхода строится "дерево поиска в ширину" с корнем <tex>s</tex>, содержащее все достижимые вершины. Для каждой достижимой их <tex>s</tex> вершины <tex>v</tex> путь в дереве поиска в ширину соответствует кратчайшему поти пути от <tex>s</tex> до <tex>v</tex> в <tex>G</tex>.
Для отслеживания работы алгоритма поиск в ширину раскрашивает вершины графа в белый, серый и черный цвета. Изначально все вершины белые, и позже они могут стать серыми, а затем черными. Когда вершина '''открывается''' в процессе поиска, она окрашивается. Таким образом, серые и черные вершины — это вершины, которые уже были открыты, но алгоритм поиска в ширину по-разному работает с ними, чтобы обеспечить объявленный порядок обхода. Если <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> в дереве поиска вширинув ширину. Посколько Поскольку вершина модет может быть открыта не более одного раза, она имеет не более одного родителя.
=== Реализация===
