Что делает: обходит граф

Где применяется: нахождение кратчайшего расстояния из одной вершины в невзвешенном графе, алгоритм Прима, алгоритм Дейкстры.

Общая идея:

Обойти все ребра графа для “открытия” всех вершин, достижимых из s, вычисляя при этом расстояние (минимальное количество ребер) до каждой вершины.

Реализация:

// псевдокод писала Я так что чекните если что не так!

Queue = ø

int main() {
	for v из G(V) do {
		v.color = white // расскрашиваем все вершинки в белый
		v.distance = ∞ // устанавливаем расстояние до вершин равным бесконечности
	}
	s.color = gray // инициализируем стартовую вершину
	s.distance = 0
	Queue.push(s) // добавляем в очередь стартовую вершину
	BFS()
}

void BFS() {
	while (Queue != ø) 
			u = Queue.front() // вытаскиваем вершину из очереди
			for v из смежных u do
				if v.color == white {
					v.color = gray
					v.distance = u.distance + 1 // поиск кратч. расстояния
					Queue.push(v) // добавляем смежные вершинки в очередь
				}
			u.color = black
}

Реализуется на **очереди!** В очередь сначала добавляется стартовая вершина, затем добавляются в очередь её смежные вершинки, завершается обход стартовой (pop при `Queue.front()`), и BFSим следующую вершинку из очереди.

Таким образом, происходит обход в ширину, т.е. мы не доходим до вершин уровня k+1, пока не пройдем все вершины на уровне k.

‼ Особенности BFS:

1. можно использовать как на ориентированных, так и на неориентированных графах
2. в процессе BFS строится дерево поиска в ширину (← тык)

Визуализация: