+C++20
C++20판은 같은 인접 리스트를 사용하고 도달 불가 거리를 -1로 둔다. 출발점과 모든 이웃 번호는 graph의 유효한 인덱스여야 한다. 벡터의 앞을 지우는 대신 head를 늘려 큐의 읽기 위치만 옮긴다.
#include <cstddef>
#include <iostream>
#include <vector>
using Graph = std::vector<std::vector<std::size_t>>;
struct SearchResult {
std::vector<std::size_t> order;
std::vector<std::ptrdiff_t> distance;
};
SearchResult breadthFirst(const Graph& graph, std::size_t start) {
SearchResult result{{}, std::vector<std::ptrdiff_t>(graph.size(), -1)};
std::vector<std::size_t> queue{start};
result.distance[start] = 0;
for (std::size_t head = 0; head < queue.size(); ++head) {
const auto from = queue[head];
result.order.push_back(from);
for (const auto to : graph[from]) {
if (result.distance[to] != -1) continue;
// 큐에 넣는 순간 표시해서 같은 정점의 중복 등록을 막는다.
result.distance[to] = result.distance[from] + 1;
queue.push_back(to);
}
}
return result;
}
int main() {
const std::vector<char> names{'A', 'B', 'C', 'D', 'E'};
const Graph 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
TypeScript