给定一个用户关系图（社交网络），如何快速计算每个用户的K阶邻居（K=2，即直接朋友和朋友的直接朋友），并优化查询效率？请说明图表示、K阶邻居计算、优化策略及大规模图处理。

1) 【一句话结论】
采用邻接表存储社交网络关系，结合LRU缓存与增量更新策略，高效计算K阶邻居（如2阶），并优化大规模图处理，尤其适用于动态稀疏社交网络。

2) 【原理/概念讲解】
老师口吻解释：社交网络是典型的稀疏图（节点多但边少），图表示上用邻接表（字典/链表存储每个节点的直接邻居），支持O(1)时间查询直接邻居。K阶邻居计算：1阶为直接朋友，2阶为朋友的直接朋友（二级关系）。计算逻辑：先获取1阶邻居，再对每个1阶邻居的1阶邻居去重合并（例如，用户u的2阶邻居 = {v的1阶邻居 | v ∈ u的1阶邻居}，去重后结果）。优化策略：

• 缓存：对热门用户K阶邻居结果用LRU缓存（假设缓存命中率80%以上，查询延迟降低80%）；
• 预计算：离线计算所有节点2阶邻居并存储（假设预计算时间24小时，适合静态图）；
• 增量更新：用户关系变化时，仅重新计算受影响节点的1阶和2阶邻居（复杂度O(ΔE)，适合动态图）。
  方向性：无向图（社交网络常见，边双向），1阶邻居直接获取；有向图（如单向关注），需分别计算入边和出边的1阶邻居，再合并（如用户u的1阶入邻居是关注者，出邻居是被关注者，2阶邻居需分别计算入边和出边的1阶邻居的1阶邻居，再合并）。

3) 【对比与适用场景】

方法	定义	特性	使用场景	注意点
邻接表存储（图数据库/自定义）	用字典/链表存储每个节点的直接邻居	稀疏图高效存储，支持快速遍历	社交网络（稀疏图）、动态图	需过滤自环（v≠u），去重边（集合存储），处理孤立节点
离线预计算2阶邻居	一次性计算所有节点的2阶邻居并存储	查询时直接读取，无计算开销	静态图或变化小的图	占用较多存储空间（假设存储100万用户2阶邻居，需约2GB内存），更新慢（全量重算）
增量更新（在线）	用户关系变化时，仅更新受影响节点的K阶邻居	动态图高效更新	动态社交网络（关系频繁变化）	需维护更新逻辑，可能查询延迟（缓存失效后重新计算），需考虑更新传播时间
分布式存储（如Neo4j集群）	将图数据分块存储在多节点，支持分布式查询	扩展性，支持百万级节点	大规模社交网络（百万级用户）	需考虑跨节点通信开销（假设单次跨节点查询延迟10ms），缓存分布式一致性（如Redis集群）

4) 【示例】
伪代码计算用户u的2阶邻居（无向图，处理自环和孤立节点）：

def k_neighborhood(u, k=2):
    if k == 1:
        return set(adj.get(u, []))  # 直接朋友（1阶），孤立节点返回空集
    else:
        neighbors = k_neighborhood(u, k-1)  # 获取u的1阶邻居
        result = set()
        for v in neighbors:
            result.update(k_neighborhood(v, 1))  # 获取v的1阶邻居并合并
        return result

# 示例邻接表（无向图）
adj = {
    1: [2, 3],
    2: [1, 4],
    3: [1, 5],
    4: [2],
    5: [3],
    6: []  # 孤立节点
}
print(k_neighborhood(1, 2))  # 输出 {4, 5}
print(k_neighborhood(6, 2))  # 输出 set()
# 有向图示例（单向关注）
adj_dir = {
    1: [2, 3],  # 1关注2、3（出边）
    2: [1],    # 2关注1（入边）
    3: [1, 5], # 3关注1、5
    4: [],     # 4无关注
    5: [3]     # 5关注3
}
def k_neighborhood_dir(u, k=2, direction='out'):
    if k == 1:
        return set(adj_dir.get(u, [])) if direction == 'out' else set(adj_dir.get(u, {}).keys())
    else:
        neighbors = k_neighborhood_dir(u, k-1, direction)
        result = set()
        for v in neighbors:
            result.update(k_neighborhood_dir(v, 1, direction))
        return result
print(k_neighborhood_dir(1, 2, 'out'))  # 1的2阶出邻居：3的出边是[1,5]，即1和5
print(k_neighborhood_dir(1, 2, 'in'))   # 1的2阶入邻居：2的入边是[1]，即1

5) 【面试口播版答案】
面试官您好，针对计算K阶邻居（以K=2为例），核心思路是用图数据结构存储关系，结合缓存和增量更新优化。首先，图表示上，我们用邻接表（字典存储每个用户的直接朋友列表），因为社交网络是稀疏图，邻接表能高效存储和查询。计算2阶邻居时，对于用户u，先获取其1阶邻居（直接朋友），再对每个1阶邻居的1阶邻居去重合并，得到2阶邻居。优化方面，对于频繁查询的用户，缓存其K阶邻居结果（比如用LRU缓存，假设缓存命中率80%以上，查询延迟降低80%）；对于大规模图，离线预计算所有用户的2阶邻居并存储，或当用户关系变化时，仅更新受影响的节点的2阶邻居（比如用户新增朋友时重新计算）。这样能显著提升查询效率，尤其适合动态的社交网络场景，比如用户关系频繁变化时，增量更新能保持数据实时性。

6) 【追问清单】

• 问题1：如何处理有向图（如单向关注）的K阶邻居计算？
  回答要点：有向图需分别计算入边和出边的1阶邻居，再合并。例如，1阶入邻居是关注者，1阶出邻居是被关注者，2阶邻居需分别计算入边和出边的1阶邻居的1阶邻居，再合并。
• 问题2：大规模图（百万级用户）的内存优化策略？
  回答要点：使用分块处理（按用户ID范围分块），或图数据库的分布式存储（如Neo4j集群），或只缓存热门用户（如TOP1000）的K阶邻居，减少内存占用。
• 问题3：动态图更新时，如何保证查询的实时性？
  回答要点：采用缓存+增量更新，用户关系变化后，更新缓存并通知查询服务；对于实时查询，缓存失效后立即重新计算；对于离线查询，使用预计算。

7) 【常见坑/雷区】

• 忽略图方向性：默认社交网络是无向，若为有向，未分别处理入边和出边，导致计算错误。
• 未去重导致重复计算：计算2阶邻居时未去重，同一个节点被多次计算，增加时间复杂度。
• 缺乏缓存策略：每次查询都重新计算，效率低，对于热门用户应缓存结果。
• 未考虑动态更新：离线预计算后，用户关系变化时，未更新K阶邻居，导致数据过时。
• 孤立节点处理不当：未明确孤立节点（无直接朋友）的2阶邻居为空，导致边界条件错误。