遍历图的顶点作为该顶点的一种方法

Question

我有一个我目前无法解决的问题。假设我有一个 class Member，其中包含有关与给定成员相关联的成员列表的信息： ArrayList<Member> links;此外，这个类还有一个方法叫做canBeLinked(Member member)，这显然返回布尔值，定义特定成员是否可以直接或间接与给定的成员链接。说“直接”是指公共关系 A -> B；如果例如 A -> B 和 B -> C，那么它也应该返回 true。还要记住，如果 A -> B，则 B -> A。所以我们得到了无向图的模型。我的困惑是如何实现这个功能；我想它一定是递归的，但关键是它不是两个参数的函数（例如，如果它是静态函数，我们可以很容易地编写 function canBeLinked(Member a, Member b)，互联网上有很多此类图的实现）。我的第一种方法是写这样的东西：public boolean canBeLinked(Member member) {   if (this.links.contains(member)) {       return true;   }   else {       for (Member m : links)           if (m.canBeLinked(member)) return true;   }   return false;}我肯定会得到一个 StackOverflowException；假设我们有这样的关系：A -> BB -> DB -> ED -> CE -> C打电话时a.canBeLinked(c) 我们得到：1）首先我们检查“c”是否已经在“a”的成员列表中；2）这不是真的，所以进入for循环；3) 因为我们在列表中只有一个成员（它是“b”），我们调用 b.canBeLinked(c); 4) "c" 也不是 "b" 列表的成员，所以它也进入了 "for" 语句 5) 现在我们有麻烦了，因为 "b" 的列表不仅包含 "e" 和 " d”，还有“a”，这将我们引向 p.1；它会永远持续下去（直到内存耗尽）你能解释一下如何解决这个问题吗？我很确定这是一个简单的方法，但我只是被它卡住了，并且肯定错过了它的一些关键点。

Answer 1

幸运的是，修复相当简单；您需要跟踪Members在您的搜索中已经访问过的内容，例如使用 a Set<Member>，而不是循环返回访问任何Members已经看过的内容。在查询链接之前，Members您将当前添加Member到访问的集合中。

由于您的递归函数现在需要传递访问过的成员集，因此最好将其拆分为您从公共方法调用的privateorprotected方法。

public boolean canBeLinked(Member member) 

{

  return canBeLinked(member, new HashSet<>());

}

private boolean canBeLinked(Member member, Set<Member> visited)

{

  if (this.links.contains(member)) {

      return true;

  }

  else {

    visited.add(this);

    for (Member m : links)

    {

      if (!visited.contains(m)) return m.canBeLinked(member, visited);

    }

  }

  return false;

}