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 discovers shortest unweighted paths in layers. Mark vertices when enqueuing, not after dequeue, to avoid duplicate frontier entries. Undirected edges need adjacency in both directions.

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.

adjacency := [][]int{{1, 2}, {0, 3}, {0, 3}, {1, 2}, {}}
distance := make([]*int, len(adjacency))
zero := 0
distance[0] = &zero
queue := []int{0}
for head := 0; head < len(queue); head++ {
	u := queue[head]
	for _, v := range adjacency[u] {
		if distance[v] == nil {
			next := *distance[u] + 1
			distance[v] = &next // Mark discovery before enqueueing.
			queue = append(queue, v)
		}
	}
}
fmt.Println(*distance[3], distance[4] == nil) // 2 true

Why unequal edge costs change the question

A FIFO frontier makes the first discovered hop count minimal. Parallel edges and self-loops do not change distances. DFS finds reachability but its first path need not be shortest. Use BFS for fewest transitions; weighted costs require another frontier policy. Build adjacency privately; a nil distance marks an unreachable member.

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.

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