BFS适合找最短人际链路，因其在无权图中按距离起点步数逐层扩展，首次访问目标时路径必最短；需用队列保证顺序、哈希集合防重复、记录父节点以回溯完整链路，并注意空间优化与连通性判断。

广度优先搜索（BFS）是找社交网络中最短人际链路的天然选择——它不靠猜测，而是靠“分层推进”的确定性逻辑，确保第一次触达目标时，路径一定最短。

为什么BFS适合找最短人际链路？
社交关系本质上是无权图：A关注B、B是C好友、C和D互粉……每条边权重都为1。BFS按“距离起点步数”逐层扩展，第1层是直接好友，第2层是好友的好友，第3层是三度好友……谁最先被访问到，谁就处在最短链路上。这不是概率，而是算法保证。

关键操作必须到位，否则结果失效

• 用队列管理探索顺序（先进先出），确保近的节点永远先处理
• 每个用户只访问一次，用哈希集合（如Python的set或Java的HashSet）标记已访问，避免循环或重复计算
• 记录路径信息，不能只判断“是否到达”，而要能回溯出完整链路

四步实现清晰可靠

• 初始化：把起始用户加入队列，同时存入其父节点（为空）和已走步数（0）
• 循环取队首：检查是否等于目标用户；若是，立即停止并重建路径
• 扩展邻居：遍历该用户所有未访问过的好友，全部入队，并记录他们的父节点是当前用户
• 路径重建：从目标用户不断查父节点，直到回到起点，再逆序输出——这就是最短人际链路

实际中要注意的细节

• 社交图常有数千万节点，BFS空间开销大，需限制最大搜索层数（例如只查到六度以内）
• 若用邻接表存储关系，查找某用户所有好友是O(1)平均时间；若用数据库实时查，会严重拖慢速度，建议预加载或缓存
• 遇到“找不到路径”时，不是算法失败，而是两人在当前图中不连通，可返回空链路或提示“无共同连接”

简单示意（以Python伪代码逻辑为例）

from collections import deque
def shortest_friend_chain(graph, start, target):
    if start == target:
        return [start]
    queue = deque([start])
    parent = {start: None}
    while queue:
        user = queue.popleft()
        for friend in graph.get(user, []):
            if friend not in parent:
                parent[friend] = user
                if friend == target:
                    # 回溯构造路径
                    path = []
                    while friend is not None:
                        path.append(friend)
                        friend = parent[friend]
                    return path[::-1]
                queue.append(friend)
    return []  # 无路径

不复杂但容易忽略