Если поиск в глубину можно назвать обходом для смелых (алгоритм идет как можно дальше от "дома"), то поиск в ширину — это обход для осторожных. Он работает "кругами", сперва посещая все вершины, смежные со стартовой, затем — вершины, которые лежат на расстоянии двух ребер от стартовой, и т.д., пока не будут посещены все вершины связного компонента, которому принадлежит стартовая точка.

Для выполнения поиска в ширину удобно использовать очередь (обратите внимание на это отличие от поиска в глубину!). Очередь инициализируется стартовой вершиной поиска, помеченной как посещенная. На каждой итерации алгоритм находит все непосещенные вершины, смежные с вершиной в начале очереди, помечает их как посещенные и вносит в очередь; после этого вершина в начале очереди изымается из нее.

class G {
	struct Edge {
		int source;
		int dest;
		int weight;
	};
	map<int, vector<Edge>> m;

	void BFS() {
		set<int> visited;
		for (auto& [k, v] : m) {
			if (!visited.contains(k)) {
				bfs(k, visited);
			}
		}
	}


	void bfs(int start, set<int> visited) {
		visited.insert(start);
		queue<int> q;
		q.push(start);
		while (!q.empty()) {
			int curVertex = q.front();
			q.pop();
			for (Edge& e : m[curVertex]) {
				if (!visited.contains(e.dest)) {
					visited.insert(e.dest);
					q.push(e.dest);
				}
			}
		}
	}
};

Стоит отметить что данный алгоритм пройдет по абсолютно всем вершинам графа в независимости от того, является он связным или нет.(компоненты связности можно отловить в первой функции, в цикле).

Вот как я привык реализовывать обход в ширину:

void BFS(char start) {
	queue<int> q;
	set<int> visited;
	q.push(start);
	while (!q.empty()) {
		char v = q.front();
		q.pop();
		visited.insert(v);
		for (Edge& e : listA[v]) {
			if (!visited.contains(e.dest)) {
				q.push(e.dest);
			}
		}
	}
}

Мой вариант пройдется только по той компоненте связности, в которой находилась стартовая точка.

Поиск в ширину имеет эффективность:

• Θ(|V|²) для матрицы смежности
• Θ(|V| + |E|) для списков смежности

Ключевые отличия от DFS:

1. Дает единственное упорядочение вершин (принцип FIFO)
2. Поперечные ребра соединяют вершины на одном или соседних уровнях
3. Оптимален для поиска кратчайших путей по количеству ребер

Особенно полезен для:

• Поиска кратчайшего пути по количеству ребер
• Проверки связности графа
• Обнаружения ацикличности