Обход в ширину

Поиск в ширину (BFS, Breadth-first search) — метод обхода и разметки вершин графа.

Алгоритм

Общая идея

Поиск в ширину реализуется с помощью структуры очередь. Для этого занесем в очередь исходную вершину. Затем, пока очередь не пуста, будем извлекать первый элемент из очереди и добавлять в конец все не посещенные смежные с ним вершины.

Реализация

Входные данные:

vector < vector<int> > g; // граф, реализованный с помощью списка смежности
int n; // число вершин
int s; // стартовая вершина (вершины везде нумеруются с нуля)
// чтение графа
...

Сам обход:

queue<int> q;
q.push (s);
vector<bool> used (n);
used[s] = true;
while (!q.empty()) {
	int v = q.front();
	q.pop();
	for (size_t i=0; i<g[v].size(); ++i) {
		int to = g[v][i];
		if (!used[to]) {
			used[to] = true;
			q.push (to);
		}
	}
}

Практические применения

• Волновой алгоритм в трассировке печатных плат;
• Поиск увеличивающего пути в Форда-Фалкерсона алгоритм|алгоритме Форда-Фалкерсон (алгоритм Эдмондса-Карпа)

Литература

• Ананий В. Левитин Глава 5. Метод уменьшения размера задачи: Поиск в ширину // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 215-218. — ISBN 0-201-74395-7
• Томас Х. Кормен и др. Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1