12
правок
Изменения
Новая страница: «'''Поиск в ширину''' ('''BFS''', Breadth-first search) — метод обхода и разметки вершин графа. ==Алгоритм== ==…»
'''Поиск в ширину''' ('''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
==Алгоритм==
===Общая идея===
Поиск в ширину реализуется с помощью структуры очередь. Для этого занесем в очередь исходную вершину. Затем, пока очередь не пуста, будем извлекать первый элемент из очереди и добавлять в конец все не посещенные смежные с ним вершины.
=== Реализация===
Входные данные:
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
