C#基于EF Core 3.1实现好友的好友中同城市非好友路径查询

前置说明 #

• 好友关系属于无向图，查询单个用户的直接好友时需要同时覆盖Member1和Member2两种关联场景
• 路径搜索采用广度优先搜索(BFS)，天然保证优先返回最短路径，可根据业务需要限制最大搜索深度（比如最多3度好友，避免性能爆炸）
• 优先过滤同城市用户再做路径匹配，可大幅降低搜索范围

步骤1：封装获取用户直接好友列表的通用方法 #

首先注入ApplicationDbContext后，先写工具方法获取指定用户的所有直接好友ID，方便后续调用：

// 获取指定用户的所有直接好友ID集合
private HashSet<int> GetDirectFriendIds(int memberId)
{
    return _context.Friends
        .Where(f => f.Member1Id == memberId)
        .Select(f => f.Member2Id)
        .Concat(_context.Friends
            .Where(f => f.Member2Id == memberId)
            .Select(f => f.Member1Id))
        .ToHashSet();
}

步骤2：实现BFS路径搜索核心逻辑 #

以下是完整的业务实现方法，入参为指定用户ID、最大搜索深度，返回符合要求的路径集合：

public List<string> SearchSameCityNonFriendWithPath(int targetMemberId, int maxDepth = 3)
{
    // 读取目标用户基础信息，为空直接返回空结果
    var targetMember = _context.Members.Find(targetMemberId);
    if (targetMember == null) return new List<string>();
    
    var directFriendIds = GetDirectFriendIds(targetMemberId);
    var result = new List<string>();
    // 记录已访问用户ID，避免循环遍历
    var visited = new HashSet<int> { targetMemberId };
    // BFS队列，每个元素存储当前用户ID、当前路径列表
    var queue = new Queue<(int MemberId, List<string> Path)>();
    
    // 队列初始化：把目标用户的直接好友先入队
    foreach (var friendId in directFriendIds)
    {
        var friend = _context.Members.Find(friendId);
        if (friend == null) continue;
        visited.Add(friendId);
        queue.Enqueue((friendId, new List<string> { targetMember.Name, friend.Name }));
    }

    // 开始BFS遍历
    while (queue.Count > 0)
    {
        var current = queue.Dequeue();
        var currentDepth = current.Path.Count - 1;
        
        // 超过最大搜索深度直接跳过
        if (currentDepth >= maxDepth) continue;
        
        // 读取当前节点的所有好友
        var currentFriendIds = GetDirectFriendIds(current.MemberId);
        foreach (var friendId in currentFriendIds)
        {
            // 已访问过的节点跳过，避免环路
            if (visited.Contains(friendId)) continue;
            visited.Add(friendId);
            
            var currentFriend = _context.Members.Find(friendId);
            if (currentFriend == null) continue;
            
            // 拼接新的路径
            var newPath = new List<string>(current.Path) { currentFriend.Name };
            
            // 校验是否符合要求：同城市、不是目标用户的直接好友、不是目标用户本人
            if (currentFriend.City == targetMember.City 
                && !directFriendIds.Contains(friendId) 
                && friendId != targetMemberId)
            {
                // 按要求格式化路径字符串
                result.Add($"{string.Join(" -- ", newPath)}(\"{targetMember.City}\")");
            }
            
            // 新节点入队，继续下一层搜索
            queue.Enqueue((friendId, newPath));
        }
    }

    return result;
}

性能优化建议 #

• 如果数据量较大，建议提前把目标城市所有用户的好友关系一次性加载到内存，避免循环查询数据库：

// 提前加载目标城市所有用户的好友关系
var targetCity = targetMember.City;
var allCityMembers = _context.Members
    .Where(m => m.City == targetCity)
    .Include(m => m.MemberFriends)
    .Include(m => m.MemberFriendsOf)
    .ToList();
// 后续所有好友查询直接从该内存集合读取，减少数据库交互次数

• 最大搜索深度建议不要超过4，否则性能会呈指数级下降
• 如果需要返回所有可能路径而非仅最短路径，去掉visited集合的判断逻辑，改为记录访问路径避免环路即可

内容的提问来源于stack exchange，提问作者uzair