+C++ 예제
C++에서는 std::queue<int>(기본 컨테이너 std::deque<int>)를 써도 되지만, 정점 수가 정해진 그래프에서는 std::vector<int>와 읽기 인덱스 head를 조합하면 연속된 메모리 블록 하나에서 캐시 친화적으로 큐를 순회할 수 있다.
#include <cstddef>
#include <iostream>
#include <utility>
#include <vector>
struct BfsResult {
std::vector<int> order;
std::vector<int> distance;
};
BfsResult breadthFirst(const std::vector<std::vector<int>>& graph, int start) {
std::vector<int> distance(graph.size(), -1);
std::vector<int> order;
std::vector<int> queue{start};
distance[start] = 0;
for (std::size_t head = 0; head < queue.size(); ++head) {
int from = queue[head];
order.push_back(from);
for (int to : graph[from]) {
if (distance[to] != -1) continue;
// 큐에 넣는 순간 거리를 기록해 중복 삽입을 막는다.
distance[to] = distance[from] + 1;
queue.push_back(to);
}
}
return {std::move(order), std::move(distance)};
}
int main() {
const char names[] = {'A', 'B', 'C', 'D', 'E'};
const std::vector<std::vector<int>> graph{{1, 2}, {3}, {3, 4}, {}, {}};
const auto result = breadthFirst(graph, 0);
for (std::size_t i = 0; i < result.order.size(); ++i) {
if (i > 0) std::cout << ',';
std::cout << names[result.order[i]];
}
std::cout << '\n';
for (std::size_t i = 0; i < result.distance.size(); ++i) {
if (i > 0) std::cout << ',';
std::cout << result.distance[i];
}
std::cout << '\n';
return 0;
}
실행 결과:
A,B,C,D,E
0,1,1,2,2