+C++ example
In C++, while std::queue<int> (backed by std::deque<int>) is standard, pairing a contiguous std::vector<int> with a advancing head index avoids chunked deque allocations when the vertex count is bounded.
#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;
// Mark on enqueue so shared neighbors are never queued twice.
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;
}
Output:
A,B,C,D,E
0,1,1,2,2