+C++20
The C++20 version uses the same adjacency list and keeps -1 for unreachable distances. The start and every neighbor must be valid indices into graph. Advancing head moves the read position without erasing the front of the vector.
#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;
// Mark on enqueue to prevent another edge from queuing the same vertex.
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