将Java版DFS好友推荐算法代码翻译为Dart实现

实现说明 #

• 核心逻辑与原Java版本完全对齐，基于深度优先搜索遍历好友关系无向图，划分连通分量后返回同社交圈内的待推荐好友
• 适配Dart 2.12+ 空安全标准，无语法报错，可直接运行
• 泛型设计支持任意用户标识类型（如int型用户ID、String型用户名等）

完整Dart代码 #

import 'dart:collection';

class SuggestFriendsDFS<T> {
  /// 邻接表存储好友关系无向图
  final HashMap<T, List<T>> _adj = HashMap<T, List<T>>();
  /// 缓存连通分量（好友圈子）结果
  final List<Set<T>> _groups = [];

  /// 添加双向好友关系
  void addFriendship(T src, T dest) {
    _adj.putIfAbsent(src, () => <T>[]);
    _adj[src]!.add(dest);
    _adj.putIfAbsent(dest, () => <T>[]);
    _adj[dest]!.add(src);
    // 新增好友关系后清空缓存，下次查询时重新计算连通分量
    _groups.clear();
  }

  /// 遍历全图找到所有连通分量（好友圈子）
  void _findGroups() {
    final Map<T, bool> visited = HashMap<T, bool>();
    // 初始化访问标记
    for (final T node in _adj.keys) {
      visited[node] = false;
    }
    // 遍历所有未访问节点启动DFS
    for (final T node in _adj.keys) {
      if (visited[node] == false) {
        final Set<T> group = HashSet<T>();
        _dfs(node, visited, group);
        _groups.add(group);
      }
    }
  }

  /// 深度优先搜索遍历单个连通分量
  void _dfs(T v, Map<T, bool> visited, Set<T> group) {
    visited[v] = true;
    group.add(v);
    for (final T neighbor in _adj[v]!) {
      if (visited[neighbor] == false) {
        _dfs(neighbor, visited, group);
      }
    }
  }

  /// 获取指定用户的推荐好友列表
  Set<T> getSuggestedFriends(T user) {
    // 无缓存时先计算所有连通分量
    if (_groups.isEmpty) {
      _findGroups();
    }
    // 找到用户所在的好友圈子
    Set<T> targetGroup = <T>{};
    for (final Set<T> group in _groups) {
      if (group.contains(user)) {
        targetGroup = group;
        break;
      }
    }
    // 移除用户自身，返回剩余同圈用户作为推荐结果
    targetGroup.remove(user);
    return targetGroup;
  }
}

使用示例 #

void main() {
  final suggest = SuggestFriendsDFS<String>();
  // 添加好友关系
  suggest.addFriendship('A', 'B');
  suggest.addFriendship('B', 'C');
  suggest.addFriendship('D', 'E');

  // 获取A的推荐好友：返回{B,C}
  print(suggest.getSuggestedFriends('A'));
  // 获取D的推荐好友：返回{E}
  print(suggest.getSuggestedFriends('D'));
}

注意事项 #

• 代码默认在新增好友关系时自动清空连通分量缓存，避免新增关系后推荐结果不更新，如果不需要该逻辑可删除addFriendship方法中的_groups.clear()语句提升性能
• 若传入不存在任何好友关系的用户ID，返回空集合
• 邻接表使用HashMap实现，遍历顺序不固定，若需要有序推荐结果可在返回结果前自行做排序处理

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