Алгоритм поиска в ширину (bfs — breadth-first search) является одним из основных алгоритмов на графах наравне с алгоритмом поиска в глубину и применяется как составная часть во многих других алгоритмах. Пример Пусть у нас есть неориентированный граф на n вершин, заданный нам в каком-либо виде (матрица смежности, список смежности или список рёбер). Также пусть нам дан номер вершины и нас просят найти расстояние в количестве пройденных рёбер от этой вершины до всех остальных. Алгоритм Добавим стартовую вершину графа в пустую очередь Пометим стартовую вершину графа как посещённую Расстояние до текущей вершины запишем равным 0 Проверим, не пустая ли очередь, если пустая, то завершим алгоритм Достанем первую вершину из очереди Посмотрим, с какими вершинами наша текущая вершина связана и которые ещё не посещены Пометим все такие вершины посещенными Добавим каждую из них в очередь Запишем для каждой из них расстояние, равным расстоянию до текущей вершины + 1 Перейдём к шагу 4 Ссылка на гифку с визуализацией BFS Ссылка на гифку с визуализацией BFS не на дереве Ссылка на гифку с визуализацией DFS и BFS на одном графе Реализация через функцию const int maxn = 1e5; bool used[maxn]; int dist[maxn]; vector<int> g[maxn]; // что-то ещё // *** void bfs(int v){ queue<int> q; // создаём пустую очередь, потребуется подключить одноимённую библиотеку used[v] = true; // помечаем стартовую вершину посещённой dist[v] = 0; // задаём расстояние от стартовой вершины до неё самой равным 0 q.push(v); // кладём стартовую вершину в очередь while(!q.empty()){ // до тех пор пока очередь не пустая int t = q.front(); // берём первую вершину из очереди q.pop(); // удаляем первую вершину из очереди for(auto to : g[t]){ // проходимся по всем вершинам, связанным с текущей if(used[to]) // если вершина уже посещена, переходим к следующей continue; used[to] = true; // помечаем вершину to посещённой dist[to] = dist[t] + 1; // задаём расстояние до вершины to как расстояние до текущей + 1 q.push(to); // кладём вершину to в очередь } } } C const int maxn = 1e5; bool used[maxn]; int dist[maxn]; vector<int> g[maxn]; // что-то ещё // *** void bfs(int v){ queue<int> q; // создаём пустую очередь, потребуется подключить одноимённую библиотеку used[v] = true; // помечаем стартовую вершину посещённой dist[v] = 0; // задаём расстояние от стартовой вершины до неё самой равным 0 q.push(v); // кладём стартовую вершину в очередь while(!q.empty()){ // до тех пор пока очередь не пустая int t = q.front(); // берём первую вершину из очереди q.pop(); // удаляем первую вершину из очереди for(auto to : g[t]){ // проходимся по всем вершинам, связанным с текущей if(used[to]) // если вершина уже посещена, переходим к следующей continue; used[to] = true; // помечаем вершину to посещённой dist[to] = dist[t] + 1; // задаём расстояние до вершины to как расстояние до текущей + 1 q.push(to); // кладём вершину to в очередь } } }