In an unweighted graph, the distance between vertices is naturally measured in hops. Direct neighbors are one hop away, while neighbors of neighbors occupy the second hop—mirroring the idea that any two individuals are linked by a short chain of connections. Each successive ring of vertices forms a discrete layer around the origin.

Breadth-First Search (BFS) discovers nodes layer by layer, using a queue to enforce First-In-First-Out ordering. Because every newly found vertex is appended to the back of the queue, the algorithm completes all nodes at distance k before inspecting any node at distance k+1. This behavior guarantees that the first path found to a target is a shortest path.

The traversal proceeds as follows:

1. Seed the queue with every neighbor of the starting vertex.
2. Remove the node at the head of the queue.
3. If it satisfies the goal predictae, halt and report success.
4. Otherwise, append each unseen adjacent vertex to the tail and mark it discovered immediately.
5. Repeat until the queue is empty.

The order in which key-value pairs are inserted in to an adjacency map does not alter the graph topology; it may only affect the tie-breaking order among vertices that share the same depth.

Consider a search beginning at origin:

• Initialize the queue with leo, mia, and noah.
• Dequeue leo; enqueue his neighbor zoe and record both as discovered.
• Dequeue mia; zoe is already known, so only liam is enqueued.
• Dequeue noah; enqueue ava and ivy.
• Dequeue zoe; she has no outgoing edges.
• Dequeue liam; he has no outgoing edges.
• Dequeue ava; her handle ends in a, so the search terminates successfully.

Omitting the discovered set would allow zoe to enter the queue twice, first through leo and again through mia. Recording vertices at enqueue time prevents duplication and protects against infinite loops in cyclic graphs.

from collections import deque

def is_target(handle: str) -> bool:
    return handle[-1] == 'a'

network = {
    'origin': ['leo', 'mia', 'noah'],
    'leo': ['zoe'],
    'mia': ['zoe', 'liam'],
    'noah': ['ava', 'ivy'],
    'zoe': [],
    'liam': [],
    'ava': [],
    'ivy': []
}

def bfs(source: str) -> bool:
    frontier = deque()
    discovered = {source}

    for neighbor in network[source]:
        frontier.append(neighbor)
        discovered.add(neighbor)

    while frontier:
        current = frontier.popleft()

        if is_target(current):
            print(f"Goal found: {current}")
            return True

        for adjacent in network.get(current, []):
            if adjacent not in discovered:
                frontier.append(adjacent)
                discovered.add(adjacent)

    return False

bfs('origin')