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

Find minimum undirected hop distances from a source while retaining null for unreachable vertices. Parallel edges and self-loops must not cause repeated discovery or incorrect distances.

Enumerating simple paths repeats common prefixes. BFS explores a complete distance layer before the next; marking at enqueue time ensures each vertex is discovered once rather than queued by several parents.

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.

BFS visits vertices in nondecreasing hop distance. Mark a vertex when enqueuing, preventing parallel edges from duplicating frontier work. Undirected input creates both adjacency directions. Final O(V+E) time and space; prototype may enumerate simple paths.

Ownership of discovery belongs to enqueue, before another incoming edge is examined:

import java.util.*;

class Example {
    public static void main(String[] args) {
        Long[] distance = {0L, null};
        Deque<Integer> queue = new ArrayDeque<>();
        distance[1] = distance[0] + 1;
        queue.addLast(1);
        assert distance[1] != null;
        assert queue.size() == 1;
    }
}

A second edge to vertex 1 can now see it is already discovered. Marking only on removal allows duplicate queue entries. The final graph construction must add both directions for each undirected edge and validate every endpoint first.

Why unequal edge costs change the question

BFS answers shortest-hop questions in unweighted networks, dependency neighborhoods, and reachability layers. Once edge costs differ, discovery order alone no longer guarantees cheapest total cost.

Vertices are 0..n-1. Return hop distances as Long values in vertex order, with source zero and unreachable null. Self-loops and parallel undirected edges are valid. Reject n <= 0, invalid source, or invalid endpoint.

Numeric arithmetic uses long; indices use int. Inputs follow the declared types and contain no null elements unless the API permits them. Preserve caller-owned collections, including on failure, and use IllegalArgumentException for the documented invalid arguments.

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