将 java DFS 算法代码翻译成 Dart

Question

我一直在做一些研究以找到合适的推荐朋友的算法。我遇到过 DFS，但我以前从未在 Dart 中实现过它。有人可以帮我把它翻译成 Dart 吗？下面是 java 代码：

public class SuggestFriendsDFS<T> {

    private HashMap<T, ArrayList<T>> adj = new HashMap<>(); //graph
    private List<Set<T>> groups = new ArrayList<>();


    public void addFriendship(T src, T dest) {
        adj.putIfAbsent(src, new ArrayList<T>());
        adj.get(src).add(dest);
        adj.putIfAbsent(dest, new ArrayList<T>());
        adj.get(dest).add(src);
    }


    //V is total number of people, E is number of connections
    private void findGroups() {
        Map<T, Boolean> visited = new HashMap<>();
        for (T t: adj.keySet())
            visited.put(t, false);
        for (T t:adj.keySet()) {
            if (!visited.get(t)) {
                Set<T> group = new HashSet<>();
                dfs(t, visited, group);
                groups.add(group);
            }
        }
    }

    //DFS + memoization
    private void dfs(T v, Map<T, Boolean> visited, Set<T> group ) {
        visited.put(v,true);
        group.add(v);
        for (T x : adj.get(v)) {
            if (!visited.get(x))
                dfs(x, visited, group);
        }
    }


    public Set<T> getSuggestedFriends (T a) {
        if (groups.isEmpty())
            findGroups();
        Set<T> res = new HashSet<>();
        for (Set<T> t : groups) {
            if (t.contains(a)) {
                res = t;
                break;
            }
        }
        if (res.size() > 0)
            res.remove(a);
        return res;
    }
}

我知道要问的太多了，但是在我尝试翻译它并最终遇到大量错误时，任何帮助将不胜感激。提前致谢！（：作为参考，this 是我找到 java 代码解释的地方。

Answer 1

我试过 https://sma.github.io/stuff/java2dartweb/java2dartweb.html 自动 Java 到 Dart 的转换，但是一旦代码有点复杂，它就不能很好地工作。

查看下面的完整转换，您可以在Dartpad

中尝试

import 'dart:collection';

class SuggestFriendsDFS<T> {
  final HashMap<T, List<T>> _adj = HashMap(); //graph
  final List<Set<T>> groups = [];

  //Time O(1), Space O(1)
  void addFriendship(T src, T dest) {
    _adj.putIfAbsent(src, () => <T>[]);
    _adj[src]!.add(dest);
    _adj.putIfAbsent(dest, () => <T>[]);
    _adj[dest]!.add(src);
  }

  //DFS wrapper, Time O(V+E), Space O(V)
  //V is total number of people, E is number of connections
  void findGroups() {
    Map<T, bool> visited = HashMap();

    for (T t in _adj.keys) {
      visited[t] = false;
    }

    for (T t in _adj.keys) {
      if (visited[t] == false) {
        Set<T> group = HashSet();
        _dfs(t, visited, group);
        groups.add(group);
      }
    }
  }

  //DFS + memoization, Time O(V+E), Space O(V)
  void _dfs(T v, Map<T, bool> visited, Set<T> group) {
    visited[v] = true;
    group.add(v);
    for (T x in _adj[v] ?? []) {
      if ((visited[x] ?? true) == false) _dfs(x, visited, group);
    }
  }

  //Time O(V+E), Space O(V)
  Set<T> getSuggestedFriends(T a) {
    if (groups.isEmpty) findGroups();

    var result = groups.firstWhere((element) => element.contains(a),
        orElse: () => <T>{});

    if (result.isNotEmpty) result.remove(a);

    return result;
  }
}

void main() {
  SuggestFriendsDFS<String> g = SuggestFriendsDFS();
  g.addFriendship("Ashley", "Christopher");
  g.addFriendship("Ashley", "Emily");
  g.addFriendship("Ashley", "Joshua");
  g.addFriendship("Bart", "Lisa");
  g.addFriendship("Bart", "Matthew");
  g.addFriendship("Christopher", "Andrew");
  g.addFriendship("Emily", "Joshua");
  g.addFriendship("Jacob", "Christopher");
  g.addFriendship("Jessica", "Ashley");
  g.addFriendship("JorEl", "Zod");
  g.addFriendship("KalEl", "JorEl");
  g.addFriendship("Kyle", "Lex");
  g.addFriendship("Kyle", "Zod");
  g.addFriendship("Lisa", "Marge");
  g.addFriendship("Matthew", "Lisa");
  g.addFriendship("Michael", "Christopher");
  g.addFriendship("Michael", "Joshua");
  g.addFriendship("Michael", "Jessica");
  g.addFriendship("Samantha", "Matthew");
  g.addFriendship("Samantha", "Tyler");
  g.addFriendship("Sarah", "Andrew");
  g.addFriendship("Sarah", "Christopher");
  g.addFriendship("Sarah", "Emily");
  g.addFriendship("Tyler", "Kyle");
  g.addFriendship("Stuart", "Jacob");

  g.findGroups();
  print(g.groups);

  String name = "Andrew";
  
  print("Suggestion friends of " +
      name +
      ": " +
      g.getSuggestedFriends(name).toString());
}

将 java DFS 算法代码翻译成 Dart

Translating java DFS algorithm code to Dart

depth-first-search

dart

flutter