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