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

Breadth-first search finds minimum hop counts in an unweighted graph. Exploring every simple path is a direct prototype but can be exponential. BFS groups the search into layers, so first discovery already gives a vertex's shortest number of edges from the source.

For an undirected edge, both directions belong in adjacency. Self-loops and repeated edges are valid; they must not create repeated discoveries or change the source's distance zero.

Discovering each person at their first layer

Mark a vertex visited when it is enqueued, not when dequeued. Every discovered-but-unprocessed vertex already has a distance, preventing parallel edges or a cycle from adding it again. An edge from a layer-d vertex discovers previously unseen neighbors at d+1. Any shorter path would have reached that neighbor from an earlier layer, so the first distance is final.

Use null for an unreachable distance. Do not test distance truthiness: the source's valid distance 0 is falsy. Also allocate a separate adjacency array for every vertex; Array(n).fill([]) makes every row reference the same shared array.

Validate graph size, source and all endpoints before using them as array indices. A head-index queue avoids repeated shift() movement. Here O(V) retained queue storage is within the documented graph-space bound.

const adjacency = Array.from({length: 3}, () => []);
adjacency[0].push(1);
console.log(adjacency[1].length); // 0: rows have independent identity
const distance = [0, null, null];
console.log(distance[0] !== null); // true: zero is a discovered distance

Why unequal edge costs change the question

Adjacency construction and traversal cost O(V+E) time and O(V+E) auxiliary storage. BFS is appropriate for unweighted shortest hops and level exploration. Weighted shortest costs need Dijkstra or another weight-aware algorithm; treating every weighted edge as one hop changes the problem.

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