Graphs and breadth-first search

A community app wants to show how many introductions connect one member to everyone else. Friendships work both ways, circles contain cycles, and some members belong to disconnected groups. The app is counting links, so every edge has the same cost.

Trying routes individually revisits the same people through many paths. Breadth-first search explores one distance layer at a time and records a person as soon as that layer discovers them.

Measuring degrees of separation

BFS finalizes hop distance when a vertex is first discovered. Every queue layer contains vertices whose distance is one greater than the preceding layer. Mark on enqueue, rather than dequeue, to avoid repeatedly adding the same vertex through parallel edges or cycles.

Discovering each person at their first layer

From member 0, discover 1 and 2 at one link, then 3 through 1 at two links. When 2 also points to 3, don't queue 3 again. Marking discovery on enqueue makes the first recorded distance final in this equal-cost model. An isolated member keeps an absent distance; zero is reserved for the source itself.

std::vector<std::optional<Int>> distance(n);
distance[source]=0;
// An engaged optional containing zero is a visited source, not an absent distance.

Why unequal edge costs change the question

Undirected input requires adding both adjacency directions. Self-loops do not improve distance, and duplicate edges must not trigger repeated discoveries. Unreachable vertices remain nullopt, so an arbitrary large number is unnecessary as an infinity sentinel. Check all endpoints before indexing the adjacency vector; caller data must never become an unchecked array index. BFS costs O(V+E) time and space, while enumerating simple paths can be exponential even though it eventually finds the same minimum hop counts.

Building adjacency and running BFS take O(V+E) time and space, including distance slots for isolated vertices. Mark a vertex when enqueuing it so parallel edges and cycles do not create repeated work. Use weighted shortest-path methods when edge costs differ.

Use the supplied Int, Vec, and Opt aliases. Numeric arithmetic fits signed long long; absence uses std::nullopt, and documented invalid inputs throw std::invalid_argument. Keep caller-owned containers unchanged.

These introduction counts measure hops, not the speed or reliability of an introduction.