如何在Node.js中实现两用户间社交分离度及关联路径查询功能

核心实现思路 #

该需求本质是无向图的全路径查找问题，好友关系为双向无权重边，基于广度优先搜索(BFS)实现即可，默认限制最大遍历深度为6，符合六度分隔理论要求。

步骤1：构建无向图邻接表 #

好友关系是双向关联，录入关系时需要双向添加邻接节点：

// 初始化邻接表存储所有用户的好友关系
const graph = new Map();

// 添加双向好友边的工具函数
function addFriendRelation(userA, userB) {
  if (!graph.has(userA)) graph.set(userA, []);
  if (!graph.has(userB)) graph.set(userB, []);
  graph.get(userA).push(userB);
  graph.get(userB).push(userA);
}

// 录入题目给出的所有好友关系
addFriendRelation('Sameer', 'Aayushi');
addFriendRelation('Aayushi', 'Bhaskar');
addFriendRelation('Sameer', 'Kamalnath Sharma');
addFriendRelation('Kamalnath Sharma', 'Shanti Kumar Saha');
addFriendRelation('Shanti Kumar Saha', 'Bhaskar');

步骤2：实现全路径查找逻辑 #

基于BFS遍历，每个队列节点存储当前遍历路径，自动过滤环路，超出最大深度直接停止扩展：

/**
 * 查找两个用户之间的所有关联路径
 * @param {string} startUser 起点用户名
 * @param {string} endUser 终点用户名
 * @param {number} maxDepth 最大遍历深度，默认6符合六度分隔要求
 * @returns {Array<string[]>} 所有符合要求的路径数组
 */
function findAllRelationPaths(startUser, endUser, maxDepth = 6) {
  const resultPaths = [];
  // BFS队列，每个元素为当前遍历的路径数组
  const queue = [[startUser]];

  while (queue.length) {
    const currentPath = queue.shift();
    const currentNode = currentPath.at(-1);

    // 到达终点，将路径加入结果集
    if (currentNode === endUser) {
      resultPaths.push(currentPath);
      continue;
    }

    // 超出最大深度，不再扩展当前路径
    if (currentPath.length >= maxDepth) continue;

    // 遍历当前用户的所有好友，生成新路径入队
    const friends = graph.get(currentNode) || [];
    for (const friend of friends) {
      // 过滤环路，避免重复访问路径中已存在的用户
      if (!currentPath.includes(friend)) {
        queue.push([...currentPath, friend]);
      }
    }
  }

  return resultPaths;
}

步骤3：功能测试与输出 #

// 测试查询Sameer到Bhaskar的所有关联路径
const paths = findAllRelationPaths('Sameer', 'Bhaskar');

// 格式化输出结果
paths.forEach(path => {
  console.log(path.join(' > '));
});

运行输出结果 #

• Sameer > Aayushi > Bhaskar
• Sameer > Kamalnath Sharma > Shanti Kumar Saha > Bhaskar

优化提示 #

• 处理大规模社交关系时，可替换为双向BFS实现，同时从起点和终点双向遍历，大幅降低遍历范围，提升查询效率
• 可对路径长度进行排序，默认输出最短路径在前的结果

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